title: rationale for std::lower_bound and std::upper_bound?
body: <p>STL provides binary search functions std::lower_bound and std::upper_bound,
  but I tend not to use them because I've been unable to remember what they do,
  because their contracts seem completely mystifying to me.</p>
  
  <p>Just from looking at the names,
  I'd guess that "lower_bound" might be short for "last lower bound",<br>
  i.e. the last element in the sorted list that is &lt;= the given val (if any).<br>
  And similarly I'd guess "upper_bound" might be short for "first upper bound",<br>
  i.e. the first element in the sorted list that is >= the given val (if any).</p>
  
  <p>But the documentation says they do something rather different from that--
  something that seems to be a mixture of backwards and random, to me.
  To paraphrase the doc:<br>
      - lower_bound finds the first element that's >= val<br>
      - upper_bound finds the first element that's > val</p>
  
  <p>So lower_bound doesn't find a lower bound at all; it finds the first <em>upper</em> bound!?
  And upper_bound finds the first <em>strict upper</em> bound.</p>
  
  <p>Does this make any sense??
  How do you remember it?</p>