# A Problem with recursion

• 09-28-2005
A Problem with recursion
i have to make a program that does quick searching and well it works fine untill someone enters a number not in the list

here is the function
Code:

```int q_search(int ray[], int find, int left, int right) {         int Pivot = (left + right) / 2;         if(ray[Pivot] > find && Pivot-left != 1)                 Pivot = q_search(ray, find, left, Pivot);         else if(ray[Pivot] < find && right-Pivot != 1)                 Pivot = q_search(ray, find, Pivot, right);                 if(ray[Pivot]==find)                 return Pivot;         if(right-Pivot==1 || Pivot-left == 1 && ray[Pivot] != find)                 return -1; }```
thx for any help
• 09-28-2005
Ancient Dragon
is it required to use recursion? its probably easier to use iterative method, which also runs faster and uses a lot less memory.
• 09-28-2005
PJYelton
I'm guessing he's required to use recursion.

Why do you check to see if Pivot-left or right-Pivot are not equal to one? Also, I'm not sure that last if statement will work the way you intend it, order of operations says to evaluate the && first and then the || second.

Heres a simple example of how this function probably doesn't work: Search for the number 2 in the simple array {0,2}. You'd call q_search(ray, 2, 0, 1). The pivot would be 0, the first if statement fails because ray[0] is less than 2, the second if statement fails because right-Pivot equals 1, the third if statement fails because ray[0] is not equal to 2 and the last if statement is true because right-Pivot equals 1 and (true || false && false)==true. It then returns -1 even though the number 2 is actually in the array.

The recursive version of the quick find is usually something like this:
Code:

```int q_search(int ray[], int find, int left, int right) {   return -1 if left>right   if left==right and ray[left] isn't the number you are looking for return -1, if it is return left   pivot=(left+right)/2   if ray[pivot] is the number you're looking for, return pivot   if ray[pivot] is greater than the number, return q_search(ray, find, left, pivot-1)   else return q_search(ray, find, pivot+1, right) }```
• 09-28-2005
c++.prog.newbie
the function works just fine until you try to search for a number that isnt in the list... so ill try using parenthesis were the order of opperation is incorrect.

thx though
• 09-28-2005
PJYelton
Okay, but trust me, search for the the number 2 in the array (0,2) and you'll get -1 ;)