Двоичный поиск (Binary search)
Все алгоритмы в этом разделе - версии двоичного поиска. Они работают с итераторами не произвольного доступа, уменьшая число сравнений, которое будет логарифмическим для всех типов итераторов. Они особенно подходят для итераторов произвольного доступа, так как эти алгоритмы делают логарифмическое число шагов в структуре данных. Для итераторов не произвольного доступа они выполняют линейное число шагов.
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);lower_bound находит первую позицию, в которую value может быть вставлено без нарушения упорядочения. lower_bound возвращает самый дальний итератор i в диапазоне [first, last) такой, что для любого итератора j в диапазоне [first, i) выполняются следующие соответствующие условия: *j < value или comp(*j, value) == true. Делается максимум log(last - first) + 1 сравнений.
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);upper_bound находит самую дальнюю позицию, в которую value может быть вставлено без нарушения упорядочения. upper_bound возвращает самый дальний итератор i в диапазоне [first, last) такой, что для любого итератора j в диапазоне [first, i) выполняются следующие соответствующие условия: !(value < *j) или comp(value, *j) == false. Делается максимум log(last - first) + 1 сравнений.
template <class ForwardIterator, class T> ForwardIterator equal_range(ForwardIterator first, ForwardIterator last, const T& value); template <class ForwardIterator, class T, class Compare> ForwardIterator equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);equal_range находит самый большой поддиапазон [i, j) такой, что значение может быть вставлено по любому итератору k в нём. k удовлетворяет соответствующим условиям: !(*k < value) && !(value < *k) или comp(*k, value) == false && comp(value, *k) == false. Делается максимум 2 * log(last - first) + 1 сравнений.
template <class ForwardIterator, class T> ForwardIterator binary_search(ForwardIterator first, ForwardIterator last, const T& value); template <class ForwardIterator, class T, class Compare> ForwardIterator binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);binary_search возвращает истину, если в диапазоне [first, last) имеется итератор i, который удовлетворяет соответствующим условиям: !(*i < value) && !(value < *i) или comp(*i, value) == false && comp(value, *i) == false. Делается максимум log(last - first) + 2 сравнений.
