title: Calculating mid in binary search
body: <p>I was reading an algorithms book which had the following algorithm for binary search:</p>
  
  <pre class="lang-java prettyprint-override"><code>public class BinSearch {
    static int search ( int [ ] A, int K ) {
      int l = 0 ;
      int u = A. length −1;
      int m;
      while (l &lt;= u ) {
        m = (l+u) /2;
        if (A[m] &lt; K) {
          l = m + 1 ;
        } else if (A[m] == K) {
          return m;
          } else {
            u = m−1;
          }
         }
         return −1;
        }
   }
  </code></pre>
  
  <p>The author says "The error is in the assignment <code>m = (l+u)/2;</code> it can lead to overflow and should be replaced by <code>m = l + (u-l)/2</code>."</p>
  
  <p>I can't see how that would cause an overflow. When I run the algorithm in my mind for a few different inputs, I don't see the mid's value going out of the array index.</p>
  
  <p>So, in which cases would the overflow occur?</p>