25 Algorithms library [algorithms]

25.4 Sorting and related operations [alg.sorting]

25.4.3 Binary search [alg.binary.search]

25.4.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: The elements e of [first,last) shall be partitioned with respect to the expression !(value < e) or !comp(value, e).

Returns: The furthermost iterator i in the range [first,last] such that for any iterator j in the range [first,i) the following corresponding conditions hold: !(value < *j) or comp(value, *j) == false.

Complexity: At most log2(last - first) + Ο(1) comparisons.