Java – fix binary search errors from Bentley’s book (programming pearl: writing the right program)

Binary search can be implemented in many ways - recursion, iteration, condition, etc I got this result from Bentley's iterative implementation of "programming pearl: writing the right program", including an error

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 an error in line M = (L U) / 2; It may cause overflow How can this binary search avoid this overflow?

Solution

Try the following:

change

m =(l u)/ 2

to

m =(u-1)/ 2l

If you consider a very large 2 ^ 31 – 1 element (the maximum value of a signed 32-bit integer), the reason why (L U) / 2 can overflow becomes obvious In this case, the first iteration is good because 2 ^ 31 – 10 is not very large, 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 I will cause overflow

In this way, we avoid adding u by first determining the relative middle position between L and U (u-l) / 2, and then add the lower number L to make it absolute Therefore, during operation, M = (U-1) / 2 L; We never exceed your value

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;
     }
}