Binary Search that can use an initial guess

From: Eric Ford (eford_at_[hidden])
Date: 2001-07-03 23:04:31

Is anybody interested in variations on lower_bound, upper_bound, and
equal_range that can use an initial guess iterator?  If so, I'm
willing to post it.  It's in the SGI STL style, so it's hard to read
(at least for me).  

It works in two stages, first finding a range that it knows includes
the desired elements, then it uses the standard stl versions to get
the final answer.  Still order log(n), but a different constant. 
Probably, slower if you guess randomly, but probably faster if you're
searching a large range and have a good idea where it is (e.g.
repeatedly interpolating a function at nearby points).