Re: Binary Search that can use an initial guess

From: ltmarrie_at_[hidden]
Date: 2001-07-05 08:17:53

Right, but it is O(log l) bound which is of primary interest so it is 
important to state this explicitly. (This is sometimes referred to 
as "finger" search.)

Consider the set_intersection algorithm, for example. If the 
arguments are random access iterators your lower_bound with hint 
algorithm can be used. This allows set_intersection to run in O(m log 
(n/m)), which is optimal.

Here's a quick sketch of the proof (which is due to Brown and Tarjan -
- see "Design and Analysis of a Data Structure for Representing 
Sorted Lists"):

Let the two sorted ranges be m and n, where m < n. Iterate over m, 
while using lower_bound_with_hint to traverse over n. We end up 
invoking lower_bound_with_hint m times, with the i-th call (1 < i < 
m) taking O(log l_i) time. To maximize the sum of the m calls choose 
the l_i to be equal, making each O(log l_i) equal to O(log (n/m)). 
This gives m calls to a routine which takes O(log (n/m)), giving the 
bound of O(m log(n/m)).

Anyway, I hope the above is clear enough. It seems that for 
set_intersection et al with random access iterators, the linear bound 
given by the standard can be improved upon... Actually, for that 
matter Brown and Tarjan describe a data structure called level-linked 
2-3 trees (I believe the binary node form of this can be used to 
implement std::set and friends) which similarly allows for fast set 
intersections.

Regards,

Laurence Marrie

--- In boost_at_y..., "Eric Ford" <eford_at_m...> wrote:
> --- 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.