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?

java algorithm overflow binary-search
Edit
Report