Binary search implementation in C

Question

int bin_search(int* a, int key)
{
    int lo = 0;
    int hi = sizeof(a)/sizeof(int) - 1;

   while(lo <=hi)
   {
        int mid = (lo + hi)/2;

        if(key < a[mid]) { hi = mid - 1;}
        else if (key > a[mid]) { lo = mid + 1;}
        else                    return mid;
    }

    return -1;
}

....

for(i = 0; i < sz; ++i)
{
    printf("%d\n", bin_search(a, i));
}

I think that I have a problem with this, but I can't understand why:

int hi = sizeof(a)/sizeof(int) - 1;

Answer 1

sizeof(a) in this case is sizeof(int*) which is 4 or 8 on most machines. The most simple solution would be passing the length of the input array. Otherwise, your code looks nifty.

Answer 2

1. As @coderodde answered, int hi = sizeof(a)/sizeof(int) - 1; is certainly wrong. Size of a is the size of a pointer, not the size of the array. Suggest

   int bin_search(int* a, int number_elements, int key) {
     int lo = 0;
     int hi = number_elements - 1;
   

2. As the array is not changed, make it const.

   int bin_search(const int* a, ...
   

3. Guard against int overflow. Below is a simple guard

   // int mid = (lo + hi)/2;
   int mid = (lo*1LL + hi)/2;
   

4. In general, I prefer to use size_t number_element rather than int as size_t is the right type to use as an array index. int may be insufficient. But then the failure mechanism of -1 needs re-thinking as size_t is some unsigned type. Perhaps:

   // Return T/F on if value was found.  Save index in *result.
   bool bin_search(int* a, size_t number_elements, int key, size_t *result) {
   

size_t is more robust, but problems can occur with mid - 1

bool bin_search(const int* a, size_t size, int key, size_t *index) {
  size_t lo = 0;
  size_t hip1 = size;  // hi plus 1

  while(lo < hip1) {
    size_t mid = (lo*1LLU + hip1 -1)/2;

    if (key < a[mid]) { hip1 = mid;}
    else if (key > a[mid]) { lo = mid + 1;}
    else {
      *index = mid;
      return true;
    }
  }
  return false;
}

Answer 3

In addition to what's been said, if you wanted to implement a completely correct binary search you would have to watch for overflow when you add hi and low.

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

Gives you back the value of the mid if your values of high and low are close to the maximum value if the data type you're using to store the number.

Answer 4

Your code is sensible, I have minor formatting suggestions:

(lo <=hi)

Should have simmetrical space, like:

(lo <= hi)

And

    if(key < a[mid]) { hi = mid - 1;}
    else if (key > a[mid]) { lo = mid + 1;}
    else                    return mid;

Should use multiple lines, like:

    if(key < a[mid]) {
         hi = mid - 1;
    } else if (key > a[mid]) {
         lo = mid + 1;
    } else {
         return mid;
    }

As people are more used to this format and will read it at a glance.