title: Where can I get a "useful" C++ binary search algorithm?
body: <p>I need a binary search algorithm that is compatible with the C++ STL containers, something like <code>std::binary_search</code> in the standard library's <code>&lt;algorithm&gt;</code> header, but I need it to return the iterator that points at the result, not a simple boolean telling me if the element exists.</p>
  
  <p>(On a side note, what the hell was the standard committee thinking when they defined the API for binary_search?!)</p>
  
  <p>My main concern here is that I need the speed of a binary search, so although I can find the data with other algorithms, as mentioned below, I want to take advantage of the fact that my data is sorted to get the benefits of a binary search, not a linear search.</p>
  
  <p>so far <code>lower_bound</code> and <code>upper_bound</code> fail if the datum is missing:</p>
  
  <pre><code>//lousy pseudo code
  vector(1,2,3,4,6,7,8,9,0) //notice no 5
  iter = lower_bound_or_upper_bound(start,end,5)
  iter != 5 &amp;&amp; iter !=end //not returning end as usual, instead it'll return 4 or 6
  </code></pre>
  
  <p><strong>Note:</strong> I'm also fine using an algorithm that doesn't belong to the std namespace as long as its compatible with containers. Like, say, <code>boost::binary_search</code>.</p>