title: Difference between basic binary search for upper bound and lower bound?
body: <p>In the article <a href="http://community.topcoder.com/tc?module=Static&amp;d1=tutorials&amp;d2=binarySearch" rel="noreferrer">http://community.topcoder.com/tc?module=Static&amp;d1=tutorials&amp;d2=binarySearch</a>, the author discusses binary search. He makes a distinction between finding the lowest value where something is true, and the highest value where something is false.
  The array being searched looks something like:</p>
  
  <p>false false false true true</p>
  
  <p>I am curious as to why these two cases are different. Why can't you just find the lowest value which is true, then subtract one to find the highest value which is false?</p>
  
  <p>Edit2: Ok, so I understand lower vs upper bound. Now, I am struggling to understand, when searching for the smallest integer greater than or equal to the query, why we can't just change the <code>if(mid&gt;query)</code> to <code>if(mid&gt;=query)</code> and have it do lower instead of upper bound.</p>
  
  <p>Edit: Here is what the article stated:</p>
  
  <p>"Now we finally get to the code which implements binary search as described in this and the previous section:</p>
  
  <pre><code>binary_search(lo, hi, p):
     while lo &lt; hi:
        mid = lo + (hi-lo)/2
        if p(mid) == true:
           hi = mid
        else:
           lo = mid+1
  
     if p(lo) == false:
        complain                // p(x) is false for all x in S!
  
     return lo         // lo is the least x for which p(x) is true
  </code></pre>
  
  <p>...</p>
  
  <p>If we wanted to find the last x for which p(x) is false, we would devise (using a similar rationale as above) something like:</p>
  
  <pre><code>binary_search(lo, hi, p):
     while lo &lt; hi:
        mid = lo + (hi-lo+1)/2    // note: division truncates
        if p(mid) == true:
           hi = mid-1
        else:
           lo = mid
  
     if p(lo) == true:
        complain                // p(x) is true for all x in S!
  
     return lo         // lo is the greatest x for which p(x) is false
  </code></pre>
  
  <p>."</p>