Re: Binary Search that can use an initial guess

From: Eric Ford (eford_at_[hidden])
Date: 2001-07-04 02:14:45

--- In boost_at_y..., "Sofus Mortensen" <list_at_l...> wrote:
> 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.

Sure.  It's O(log(n)) worst case (l~n), O(1) best case (l~1). 
Actually for equals_range, the lower limit to the order is set by the
size of the range found.