title: Is the following binary search code correct or incorrect? (of the book Programming Interviews Exposed)
body: <p>The recursive version of the binary search in the book:</p>
  
  <pre><code>int binarySearch(int[] array, int target) throws BSException { return int binarySearch(int[] array, int target) throws BSException { 
      return binarySearch(array, target, 0, array.length-1);
  }
  
  int binarySearch( int[] array, int target, int lower, int upper ) throws BSException {
      int center, range;
  
      range = upper - lower; 
  
      if( range &lt; 0 ){
          throw new BSException("Limits reversed");
      } else if( range == 0 &amp;&amp; array[lower] != target ){ 
          throw new BSException("Element not in array");
      }
  
      if( array[lower] &gt; array[upper] ){
          throw new BSException("Array not sorted"); 
      }
      center = ((range)/2) + lower; 
      if( target == array[center] ){
          return center;
      } else if( target &lt; array[center] ){
          return binarySearch( array, target, lower, center - 1 ); 
      } 
      else {
          return binarySearch( array, target, center + 1, upper ); 
      }
  }
  </code></pre>
  
  <p>and the iterative version:</p>
  
  <pre><code>while( true ){
      range = upper - lower;
  
      if( range == 0 &amp;&amp; array[lower] != target ){
          throw new BSException("Element not in array");
      }
  </code></pre>
  
  <p>About every other algorithm book, include TAOCP by Donald Knuth, Algorithm Design Manual, Programming Pearl, etc, has "valid case" of</p>
  
  <pre><code>while (low &lt;= high) {
      // ...
  }
  return -1;  // not found
  </code></pre>
  
  <p>or a "not found" case of <code>low &gt; high</code>:</p>
  
  <pre><code>if (low &gt; high) return -1;   // not found
  </code></pre>
  
  <p>but the recursive and iterative algorithm in the book Programming Interviews Exposed used <code>low &gt; high</code> (meaning <code>range &lt; 0</code>) as <code>BSException("Limits reversed")</code> and <code>low == high</code> to check for "not found". Now, if <code>range</code> is in fact less than 0, then the program would have thrown the exception of <code>BSException("Limits reversed")</code> and never be able to report NotFound.</p>
  
  <p>Consider the case of an array with just 2 elements, or the <code>lower</code> and <code>upper</code> only include 2 elements, say</p>
  
  <pre><code>lower is 0
  upper is 1
  center is (1-0)/2 + 0 = 0
  </code></pre>
  
  <p>Now, let's say <code>target</code> is less than <code>array[center]</code>, then <code>upper = center - 1</code> and is <code>-1</code>, while <code>lower</code> stays as <code>0</code>. So we have <code>upper &lt; lower</code> meaning <code>range &lt; 0</code> but the recursive algorithm reports it as <code>BSException("Limits reversed")</code> rather than NotFound, while the iterative doesn't see <code>lower == upper</code> and go further with <code>upper</code> as <code>-1</code> and use <code>array[upper]</code> and have strange behavior?</p>