RE: [boost] Binary Search that can use an initial guess

From: Paul A. Bristow (pbristow_at_[hidden])
Date: 2001-07-05 05:45:56

SounDr Paul A Bristow, hetp Chromatography
Prizet Farmhouse
Kendal, Cumbria
LA8 8AB      UK
[phone]
mailto:pbristow_at_[hidden]
 ds very useful when it can be used.

Yes please.

Paul

> -----Original Message-----
> From: Eric Ford [mailto:eford_at_[hidden]]
> Sent: Wednesday, July 04, 2001 5:05 AM
> To: boost_at_[hidden]
> Subject: [boost] Binary Search that can use an initial guess
> 
> 
> 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).