title: C: Two different binary search implementation, one stuck in infinite loop
body: <p>Here are two implementation of "forgetful" binary search, since they don't check for the exact match until they're finished.</p>
  
  <p>1)</p>
  
  <pre><code>int bsearch1(int A[], int n, int target)
  {
      int low = 0, high = n - 1, mid = 0;
      while (low &lt; high)
      {
          mid = (low + high) &gt;&gt; 1;
          if (target &gt; A[mid])
              low = mid + 1;
          else
              high = mid;
      }
      if (low == high)
      {
          if (A[low] == target)
              return low;
      }
  
      return -1;
  }
  </code></pre>
  
  <p>2)</p>
  
  <pre><code>int bsearch2(int A[], int n, int target)
  {
      int low = 0, high = n - 1, mid = 0;
      while (low &lt; high)
      {
          mid = (low + high) &gt;&gt; 1;
          if (target &lt; A[mid])
              high = mid - 1;
          else
              low = mid;
      }
      if (low == high)
      {
          if (A[low] == target)
              return low;
      }
  
      return -1;
  }
  </code></pre>
  
  <p>NOTES: <code>n</code> is the length of array A, <code>target</code> is the element to find.</p>
  
  <p><code>bsearch1</code> works fine, but <code>bsearch2</code> runs into infinite loop, e.g A=[1,3,5,6], target=5. The diff between them is the conditional statement in while loop, the one in <code>bsearch2</code> is just the opposite of <code>bsearch1</code>. Both are perfectly right in logic. How can I know in advance <code>bsearch2</code> is "wrong"? Can any one prove that the conditional statement in <code>bsearch2</code> will lead to infinite loop (maybe in a mathematic view)? I can't find any clues and evidences until now.</p>
  
  <p>EDIT:
  I have evaluated the whole process of the example A=[1,3,5,6], target=5:</p>
  
  <p>1.low = 0, high = 3, mid = 1, A[mid] = 3<br/>
  2.low = 1, high = 3, mid = 2, A[mid] = 5<br/>
  3.low = 2, high = 3, mid = 2, A[mid] = 5<br/>
  ...<br/>
  n.low = 2, high = 3, mid = 2, A[mid] = 5</p>
  
  <p>I found that <code>bsearch2</code> can not reach to <code>low == high</code> this condition, thus can not exit the while loop. But I don't know why <code>low</code> and <code>high</code> can not reach to <code>low == high</code> in the end likes <code>bsearch1</code>.</p>