# Binary Search is giving me a segfault

2558 views
2

I'm trying to run this implementation of binary search. I don't know why but it keeps giving me segfault error. I'm thinking the problem might be either the way I'm passing the array or there's something wrong with the recursive calls.

``````#include <stdio.h>

int hasBinarySearch(int *array, int low, int high, int element)
{

int mid = (low + (high-low)) / 2;

if (high>=low)
{

if (array[mid] == element)
{
return mid;
}
else if(array[mid]<element)
{
return hasBinarySearch(array, low, mid-1, element);
}
else
{
return hasBinarySearch(array, mid+1, high, element);
}
}

return 0;
}

int main(void)
{
int array = {1,2,3,4,5,6,6,6,7,8};
hasBinarySearch(array, 0, 9, 2);

return 0;
}
``````

your calculation `int mid = (low + (high-low)) / 2;` doesn't reliably return an integer value; mid could end up being `0` and calling with `mid-1` (`0-1`) would be unexpected behavior.

`(low + (high-low))` is just `high`. So your recursive call is doing the same thing over and over until you run out of memory.

`int mid = (low + (high-low)) / 2;` --> `int mid = low + (high-low) / 2;`

8

I think that you have some misunderstanding about binary search. Read some article or book about it.

As @Claies commented, calculation of middle index is wrong. It should be low + (high - low) / 2. Just think about the internal division of two points in mathematics.

Also, you have to fix the parameters on recursive calls like the code below.

``````#include <stdio.h>

int hasBinarySearch(int *array, int low, int high, int element)
{

int mid = low + (high - low) / 2; // changed
printf("%d %d\n", high, low);
if (high >= low)
{
if (array[mid] == element)
{
return mid;
}
else if (array[mid] < element)
{
return hasBinarySearch(array, mid + 1, high, element); // changed
}
else
{
return hasBinarySearch(array, low, mid - 1, element); // changed
}
}
return 0;
}

int main(void)
{
int array = { 1,2,3,4,5,6,6,6,7,8 };
hasBinarySearch(array, 0, 9, 2);
return 0;
}
``````

posted this
0

`mid`'s calculation simplifies to `high / 2` because you've added and then subtracted the lower bound out again. It should be just `(low + high) / 2`.

I think that segfault is happening when `high` goes below `low` and gets too small and you fall off the beginning of the array.

And @paganinist is right about the upper and lower cases being backwards.

posted this