Ryan D. - 2 months ago 14

C Question

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.

Source (Stackoverflow)

Comments