Syntax:

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

The upper_bound() algorithm searches the ordered range [start,end] for the last location that val could be inserted without disrupting the order of the range; or, equivalently, it returns the iterator to the first element that is greater than val, or “end” if no element is greater than val. This function requires the elements to be in order.

If the strict weak ordering function object cmp is given, it is used to compare elements instead of the < operator.

upper_bound() runs in logarithmic time for containers that support random access, and in linear time for all other containers. It always makes O(log n) comparisons, though.

Related Topics: binary_search, equal_range, lower_bound