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.
Comet - Grunge free COM programming in C++
> -----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:
> Your use of
> Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk