Binary Search is giving me a segfault

2541 views c
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[10] = {1,2,3,4,5,6,6,6,7,8};
  hasBinarySearch(array, 0, 9, 2);

  return 0;
}

answered question

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;

2 Answers

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[10] = { 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

Have an answer?

JD

Please login first before posting an answer.