Binary Search

Jon Bentley, in his book Programming Pearls reported that he assigned binary search in a course for professional pro-
grammers and found that 90% percent failed to code it correctly despite having ample time. (Bentley’s students would have been gratified to know that his own published implementation of binary search, in a chapter titled “Writing Correct Programs”, contained a bug that remained undetected for over twenty years.) Binary search can be written in many ways—recursive, iterative, different idioms for conditionals, etc. Here is an iterative implementation adapted from Bentley’s book, which includes his bug.

public class BinSearch {
  static  int search(int[] A, int K ) {
      int l = 0;
      int u = A.length-1;
      int m;
      while(l <= u){
         m = (l+u)/2 ;
          if(A[m] < K) {
              l = m + 1;
          } else if (A[m] == K) {
              return m;
          } else {
              u = m-1;
          }
      }
      return -1;
  }
}
 

    The error is in the assignment m = (l+u)/2; it can lead to overflow and should be replaced by m = l + (u-l)/2.The time complexity of binary search is given by B(n) = c + B(n/2).This solves to B(n) = O(log n), which is far superior to the O(n) approach needed when the keys are unsorted. A disadvantage of binary search is that it requires a sorted array and sorting an array takes O(n log n) time. However if there are many searches to perform, the time taken to sort is not an issue.

static int modifiedBinarySearch(int[] a, int length, int value) {
  int low = 0;
  int high = length;
  while (low < high) {
   int mid = (low + high) / 2;
   if (a[mid] < value)
    low = mid + 1;
   else
    high = mid;
  }
  if ((low < length) && (a[low] == value))
   return low;
  else
   return -1;
 }