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);
template<
    class ForwardRange,
    class Value,
    class SortPredicate
    >
typename range_iterator<ForwardRange>::type
lower_bound(ForwardRange& rng, Value val, SortPredicate pred);
template<
    range_return_value re,
    class ForwardRange,
    class Value,
    class SortPredicate
    >
typename range_return<ForwardRange,re>::type
lower_bound(ForwardRange& rng, Value val, SortPredicate pred);

Description

Версии lower_bound, возвращающие итератор, возвращают первый итератор в диапазоне rng таким образом, что: без предиката - *i < значение является ложным с предикатом - pred(*i, значение) является ложным.

end(rng) возвращается, если такой итератор не существует.

Версии lower_bound, возвращающие range_return, определяют found таким же образом, как и возвращенный итератор, описанный выше.

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 сортируется в порядке возрастания по оператору<.

For the predicate versions:

rng сортируется в порядке возрастания согласно pred.

Complexity

Для диапазонов, которые моделируют диапазон доступа Random Понятие сложности O(log N), где N distance(rng).

Для всех других типов диапазона сложность составляет O(N).