-
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
-
is it required to use recursion? its probably easier to use iterative method, which also runs faster and uses a lot less memory.
-
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)
}
-
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
-
Okay, but trust me, search for the the number 2 in the array (0,2) and you'll get -1 ;)