Ryan D. Ryan D. - 2 months ago 14
C Question

Binary Search Seg Fault

I'm trying to implement a binary search in a slightly non-traditional way by using only 3 arguments int value (what I'm looking for), int values[] (the array), int n (the size of the array). The code below finds the number 2 and recognizes that 13 is not there, but cannot find numbers like 6 or 7. I think the problem is in the final recursive call, but I'm not sure what to do about it. Any thoughts on where I might be going wrong would be appreciated.

#include <stdio.h>
#include <stdbool.h>

bool search(int value, int values[], int n);

int main(void)
{
int value = 6;
int values[] = {1, 2, 3, 4, 5, 6, 7};
int n = 7;

bool x = search(value, values, n);

if (x == true)
printf("found\n");
else
printf("not found\n");
}

bool search(int value, int values[], int n)
{
int midpoint = n/2;

if (n/2 <= 0)
{
return false;
}
if (value == values[midpoint])
{
return true;
}
if (value < values[midpoint])
{
return search(value, values, n/2);
}
else if (value > values[midpoint])
{
return search(value, values, n/2);
}

return false;
}

Answer

Yes, the problem is that when you call search with the upper half of the array, you should pass it with the offset like

return search(value, values + (n + 1) / 2, n / 2);

Note that I also skipped the middle element that you have already compared for the cases when n is odd. You can of course optimize the recursive calls, always taking care that also the length is calculated correctly.

Comments