28 Algorithms library [algorithms]

28.7 Sorting and related operations [alg.sorting]

28.7.3 Binary search [alg.binary.search]

Все алгоритмы в этом разделе являются версиями двоичного поиска и предполагают, что просматриваемая последовательность разделена по отношению к выражению, сформированному путем привязки ключа поиска к аргументу неявной или явной функции сравнения. Они работают с итераторами с неслучайным доступом, сводя к минимуму количество сравнений, которое будет логарифмическим для всех типов итераторов. Они особенно подходят для итераторов с произвольным доступом, поскольку эти алгоритмы выполняют логарифмическое количество шагов через структуру данных. Для итераторов с неслучайным доступом они выполняют линейное количество шагов.

28.7.3.1 lower_­bound [lower.bound]

template<class ForwardIterator, class T> ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value); template<class ForwardIterator, class T, class Compare> ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);

Requires: Элементы e из [first, last) должны быть разделены по отношению к экспрессии e < value или comp(e, value).

Returns: Самыйi дальний итератор в диапазоне, [first, last] такой, что для каждого итератора j в диапазоне [first, i) выполняются следующие соответствующие условия: *j < value или comp(*j, value) != false.

Complexity: Максимум log2(last - first)+O(1) сравнений.

28.7.3.2 upper_­bound [upper.bound]

template<class ForwardIterator, class T> ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value); template<class ForwardIterator, class T, class Compare> ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);

Requires: Элементы e из [first, last) должны быть разделены по отношению к экспрессии !(value < e) или !comp(​value, e).

Returns: Самыйi дальний итератор в диапазоне, [first, last] такой, что для каждого итератора j в диапазоне [first, i) выполняются следующие соответствующие условия: !(value < *j) или comp(value, *j) == false.

Complexity: Максимум log2(last - first)+O(1) сравнений.

28.7.3.3 equal_­range [equal.range]

template<class ForwardIterator, class T> pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, const T& value); template<class ForwardIterator, class T, class Compare> pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);

Requires: Элементы e из [first, last) должны быть разделены относительно выражений e < value и !(value < e) или comp(e, value) и !comp(value, e). Кроме того , для всех элементов e из [first, last), e < value влечет !(value < e) или comp(e, value) влечет !comp(value, e).

Returns:

make_pair(lower_bound(first, last, value),
          upper_bound(first, last, value))

или

make_pair(lower_bound(first, last, value, comp),
          upper_bound(first, last, value, comp))

Complexity: Максимум 2log2(last - first)+O(1) сравнений.

28.7.3.4 binary_­search [binary.search]

template<class ForwardIterator, class T> bool binary_search(ForwardIterator first, ForwardIterator last, const T& value); template<class ForwardIterator, class T, class Compare> bool binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);

Requires: Элементы e из [first, last) разделены относительно выражений e < value и !(value < e) или comp(e, value) и !comp(value, e). Кроме того , для всех элементов e из [first, last), e < value предполагает !(value < e) или comp(e, value) подразумевает !comp(value, e).

Returns: true еслиi в диапазоне есть итератор [first, last) , удовлетворяющий соответствующим условиям: !(*i < value) && !(value < *i) или comp(*i, value) == false && comp(value, *i) == false.

Complexity: Максимум log2(last - first)+O(1) сравнений.