Binary search is very delicate.

Here is a different version that defers detection of equality.


// inclusive indices
//   0 <= imin when using truncate toward zero divide
//     imid = imin+(imax-imin)/2;
//   imin unrestricted when using truncate toward minus infinity divide (care overflow)
//     imid = (imin+imax)>>1; or
//     imid = (int)floor((imin+imax)/2.0);
int binary_search(int A[], int key, int imin, int imax)
{
  // continually narrow search until just one element remains
  while (imin < imax)
    {
      int imid = midpoint(imin, imax);
 
      // code must guarantee the interval is reduced at each iteration
      assert(imid < imax);
      // note: 0 <= imin < imax implies imid will always be less than imax
 
      // reduce the search
      if (A[imid] < key)
        imin = imid + 1;
      else
        imax = imid;
    }
  // At exit of while:
  //   if A[] is empty, then imax < imin
  //   otherwise imax == imin
 
  // deferred test for equality
  if ((imax == imin) && (A[imin] == key))
    return imin;
  else
    return KEY_NOT_FOUND;
}


This does not use the == check inside loop, because the == branch usually only infrequently happen. No more early termination now. It always takes log(n) time.

The advantage is that if the array contains duplicates, then this can return the smallest index of the duplicated keys.

See more at http://en.wikipedia.org/wiki/Binary_search_algorithm