upper_bound

Синтаксис:

    #include <algorithm>
    forward_iterator upper_bound( forward_iterator start, forward_iterator end, const T& val );
    forward_iterator upper_bound( forward_iterator start, forward_iterator end, const T& val, StrictWeakOrdering cmp );

Алгоритм upper_bound() ищет в упорядоченном диапазоне [start,end) последнюю позицию, в которую можно вставить значение val сохраняя упорядоченность. Во втором случае функция возвращает итератор на первый элемент, который больше val (элементы должны быть упорядочены).

Если нужна повышенная точность, вводится упорядочивающая функция-объект cmp, которая используется для сравнения двух объектов вместо оператора <.

upper_bound() работает за логарифмическое время для контейнеров, поддерживающий случайный доступ, и за линейное время для остальных контейнеров. Функция всегда производит O(log n) сравнений.

Смотрите также: binary_search, equal_range, lower_bound