Binary Search is giving me a segfault

Question

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;
}

Answer 1

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;
}

Answer 2

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

@paganinist good answer points out the flaws in OP's search method and with a fix.

---

Yet to dig deeper.

Even though some compilers might be able to "un-recurse" code (Example), recursion is not needed here. A simple loop will suffice.

Array sizes can approach near maximum or exceed the range of int in extreme cases.
For sizes in the high int range, the following is better. @Jonathan Leffler

// int mid = (low + high)/2;  // could overflow
int mid = low + (high-low)/2; // better, will not overflow when low >= 0

To accommodate all array sizes, use size_t instead on int. This also handles sizes including those near and above INT_MAX.

---

Candidate solution that returns the address of the matching element or NULL if not found.

#include <stdlib.h>
#include <stdio.h>

int *BinarySearch_int(const int *array, size_t count, int key) {
  while (count > 0) {
    size_t mid = count / 2;
    if (key > array[mid]) {
      array += mid + 1;
      count -= mid + 1;
    } else if (key < array[mid]) {
      count = mid;
    } else {
      return (int *) &array[mid];
    }
  }
  return NULL;
}

Test code

bool BinarySearch_int_test(const int *array, size_t count, int key, bool target){
  int *p = BinarySearch_int(array, count, key);
  bool success = (p != NULL) == target && (p == NULL || *p == key);
  printf("f(Array:%p count:%zu, key:%2d) --> ptr:%p value:%2d success:%d\n",
      (void*) array, count, key, (void*) p, p ? *p : 0, success);
  return success;
}

int main(void) {
  int array[] = {10, 20, 30, 40, 50, 60};
  size_t n = sizeof array / sizeof array[0];
  for (size_t i = 0; i < n; i++) {
    BinarySearch_int_test(array, n, array[i], 1);
  }
  BinarySearch_int_test(array, n, 0, 0);
  for (size_t i = 0; i < n; i++) {
    BinarySearch_int_test(array, n, array[i] + 1, 0);
  }
}

Output

f(Array:0xffffcb90 count:6, key:10) --> ptr:0xffffcb90 value:10 success:1
...
f(Array:0xffffcb90 count:6, key:60) --> ptr:0xffffcba4 value:60 success:1
f(Array:0xffffcb90 count:6, key: 0) --> ptr:0x0 value: 0 success:1
...
f(Array:0xffffcb90 count:6, key:61) --> ptr:0x0 value: 0 success:1

Answer 3

mid's calculation simplifies to high / 2 because you've added and then subtracted the lower bound out again. It looks like you meant to add half the difference to the lower bound, but the division occurs too late. It should be low + (high-low) / 2. (This is a bit more complicated than (low + high) / 2 but avoids the integer-math problem mentioned elsewhere.)

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.