Your Binary Search Implementation Is Wrong

I've lost count of how many times I've written:

     public static int binarySearch(int[] a, int key) {
         int low = 0;
         int high = a.length - 1;

         while (low <= high) {
             int mid = (low + high) / 2;
             int midVal = a[mid];

             if (midVal < key)
                 low = mid + 1
             else if (midVal > key)
                 high = mid - 1;
             else
                 return mid; // key found
         }
         return -(low + 1);  // key not found.
     }

On someone else's whiteboard, usually as a warm up to something more complicated.

Turns out every time I wrote that I was wrong (along with most everyone else). Why? The bug is in this line:

int mid = (low + high) / 2;

Why? Our good friends at google research pointed this out few years ago. Good read it to find out what the bug is and then do it right next time someone asks you to whiteboard binary search (or most other divide and conquer algorithms).

http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html