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

From: Sofus Mortensen (list_at_[hidden])
Date: 2001-07-04 01:19:43

I think it is better than O( log(n) ). Finding the range shouldn't take
more than O( log(l ) ), where l is the distance between the guess and
sought element. Searching the range is O( log(l) ) too, since the range
will have no more than l elements.

Best regards,

Sofus Mortensen

Comet - Grunge free COM programming in C++
http://www.lambdasoft.dk/comet 

> -----Original Message-----
> From: Eric Ford [mailto:eford_at_[hidden]] 
> Sent: Wednesday, July 04, 2001 6: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).
> 
> 
> 
> 
> Info: http://www.boost.org  Unsubscribe: 
> <mailto:boost-unsubscribe_at_[hidden]> 
> 
> Your use of 
> Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/ 
> 
> 
>