 # Boost :

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.