Fixing Binary search bug from Bentley's book (programming pearls: writing correct programs)

Question

Binary search can be implemented in many ways-recursive, iterative, conditionals, etc. I took this from Bentley's book "Programming pearls: Writing correct programs" which is an iterative implementation, and that includes a 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;
    }
}

I found a bug in the line m = (l+u) /2; it can lead to overflow. How can we avoid this overflow in this binary search?

Answer 1

Try the following:

change

m = (l+u) /2

to

m = (u-l) / 2 + l

The reason why the (l+u) / 2 can overflow becomes obvious if you consider a very large array of 2^31 - 1 elements (maximum value a signed 32-bit integer can hold). In this case the first iteration is just fine because 2^31 - 1 + 0 is not a big deal but consider the case of l = m + 1 here. In the second iteration u is still the same and l is 2^31 / 2 so l + u will lead to an overflow.

This way we are avoiding the addition of u + l by first determining the relative middle between l and u (u - l) / 2 and then adding the lower number l to it so it becomes absolute. So during the operation m = (u-l) / 2 + l; we never exceed the value of u.

To summarize the complete code:

public class BinSearch 
{
    static int search( int [] A, int K ) 
    {
        int l = 0;
        int u = A. length -1;
        int m;

        while ( l <= u ) 
        {
            m = (u-l) / 2 + l;

            if (A[m] < K)
                l = m + 1;
            else if (A[m] == K)
                return m;
            else
                u = m - 1;
        }
        return -1;
     }
}