Trying out a recursive binary search algorithm, it returns the correct target that I pass it but at the wrong index.
The index seems to always be the center index of the high and low values.
I added some printf's in the binarySearch if statements, and it seams it never calls itself recursively, always returns with the mid value.
Even if you change the target to a value not held within the array, it returns with index 5, and the correct target value.
int main(void)
{
int const numbers[10] = {1,3,4,7,13, 14, 17, 18, 20, 23};
int const target = 20;
int result = 0;
result = binarySearch(&numbers, 0, 10, target);
if (result != -1)
{
printf("Element is found in array in index: %d, and holds value: %d\n", result + 1, numbers[result]);
}
else
{
printf("Element is not found in array\n");
}
}
int binarySearch(int* arr, int low, int high, int x)
{
if (high >= low)
{
int mid = low + (high - low) / 2;
if (arr[mid] = x)
{
printf("mid\n");
return mid;
}
else if (arr[mid] > x)
{
printf("high\n");
return binarySearch(arr, low, mid - 1, x);
}
else if (arr[mid] < x)
{
printf("low\n");
return binarySearch(arr, mid + 1 , high, x);
}
}
else
{
return -1;
}
}
OUTPUT
Element is found in array in index: 5, and holds a value of: 20
Thoughts?
if (arr[mid] = x)? Did you mean==?if (arr[mid] = x),xis assigned toarr[mid], the result of the expression is the new value ofarr[mid], ie 20 in this case, which is true as far as C is concerned. With==, on the other hand, the expression returns1if the values on either side are equal. It's a standard gotcha in C. FWIW, doing a binary chop by recursion is a little exotic -- a loop will do the job.binarySearch()should be0, 9not1, 10-- C arrays are0origin. You need to think carefully about whatlowandhighrefer to inbinarySearch().sizeof(numbers)will give you the size of the array in bytes, in this case, probably 40.sizeof(numbers)/sizeof(numbers[0])will give you the size of the array in elements, in this case 10. Noting that that's the size allocated, not the number of elements in your static initialisation{ 1, 3, ... }. I'd change thebinarySearch()to takeconst int* arrparameter -- which would then be consistentconst numbers[]argument.