Boost C++ Libraries Home Libraries People FAQ More

PrevUpHomeNext
lower_bound
Prototype

template<class ForwardRange, class Value>
typename range_iterator<ForwardRange>::type
lower_bound(ForwardRange& rng, Value val);

template<
    range_return_value re,
    class ForwardRange,
    class Value
    >
typename range_return<ForwardRange, re>::type
lower_bound(ForwardRange& rng, Value val);

Description

The versions of lower_bound that return an iterator, returns the first iterator in the range rng such that: without predicate - *i < value is false, with predicate - pred(*i, value) is false.

end(rng) is returned if no such iterator exists.

The versions of lower_bound that return a range_return, defines found in the same manner as the returned iterator described above.

Definition

Defined in the header file boost/range/algorithm/lower_bound.hpp

Requirements

For the non-predicate versions:

For the predicate versions:

Precondition:

For the non-predicate versions:

rng is sorted in ascending order according to operator<.

For the predicate versions:

rng is sorted in ascending order according to pred.

Complexity

For ranges that model the Random Access Range concept the complexity is O(log N), where N is distance(rng).

For all other range types the complexity is O(N).


PrevUpHomeNext