Все алгоритмы в этом разделе являются версиями двоичного поиска и предполагают, что просматриваемая последовательность разделена по отношению к выражению, сформированному путем привязки ключа поиска к аргументу неявной или явной функции сравнения. Они работают с итераторами с неслучайным доступом, сводя к минимуму количество сравнений, которое будет логарифмическим для всех типов итераторов. Они особенно подходят для итераторов с произвольным доступом, поскольку эти алгоритмы выполняют логарифмическое количество шагов через структуру данных. Для итераторов с неслучайным доступом они выполняют линейное количество шагов.
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.
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.
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))
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.