## Name

upper_bound function template — Finds upper bound for a value’s position in a sorted range using binary search

## Synopsis

```template<typename FwdIter, typename T>
FwdIter upper_bound(FwdIter first, FwdIter last, const T& value);
template<typename FwdIter, typename T, typename Compare>
FwdIter upper_bound(FwdIter first, FwdIter last, const T& value, Compare comp);```

The `upper_bound` function template determines where `value` belongs in the sorted range [`first`, `last`). The return value is an iterator that points to one past the last (rightmost) occurrence of `value` in the range, if `value` is present. Otherwise, the iterator points to the last position where you can insert `value` and preserve the sorted nature of the range.

The first form compares values using the `<` operator. The second form calls `comp(*iter`, `value)`.

Figure 13-4 (under `equal_range`) shows an example of finding the bounds for the value `36`. The `upper_bound` function returns `ub` as the upper bound of `36` in the given range. Note that it returns `ub` as the upper bound for all values in the range [`36`, `41`]. For values in the range [`19`, `35`], the upper bound is equal to `lb`.

## Technical Notes

Precondition: !(*(i + 1) < *i) for all i in [first, last - 1).

The `upper_bound` function template returns first + n, in which n is the highest value in [0, last - first) such that *(first + m) < value is false for all m in [0, n).

Complexity is logarithmic. The number of comparisons is at most log(last - first) + 1. Although the iterator can be a forward iterator, ...

Get C++ In a Nutshell now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.