CKTIS / C++
std::upper_bound — the boundary after equivalent elements
`std::upper_bound` finds the partition boundary for the search value: it returns an iterator to the first element for which `value` compares less than that element, or `last` if no such element exists. With the default comparison on numbers sorted in ascending order, this is the first number greater than `value`.
Version: C++23; repository compiler flag, production runtime not attested
Syntax
#include <algorithm>
std::upper_bound(first, last, value)
std::upper_bound(first, last, value, comp)std::upper_bound, declared in <algorithm>, searches the half-open range [first, last). With the default comparison in an ascending range, it returns the first element greater than value, skipping all duplicates of that value. The result is an iterator, not an index or a membership flag. If there is no qualifying element, including in an empty range, the result is last. Check the result against last before dereferencing it.
The overload taking comp finds the first element e for which comp(value, e) is true. Its precondition requires a partition: all elements satisfying !comp(value, e) must precede all remaining elements. Full sorting under a compatible ordering is sufficient, but unnecessary for a single query. Do not search arbitrarily unordered data: violating the precondition causes undefined behavior. “Greater” depends on the comparator, not necessarily numeric >.
For an ascending range, std::lower_bound finds the first element not less than value, whereas std::upper_bound finds the first greater element. In a sorted range, these boundaries delimit the elements equivalent under the comparison. Notice the argument direction: std::upper_bound uses comp(value, element), not comp(element, value).
At least forward iterators are required. The number of comparisons is O(log N), but iterator steps can be O(N) without random access; with std::vector iterators, the step count is logarithmic. The example uses C++23-compatible syntax. The linked working draft evolves and may contain newer declarations.
Examples
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
const std::vector<int> values{1, 2, 2, 2, 4, 7};
const auto it = std::upper_bound(values.begin(), values.end(), 2);
std::cout << "index=" << (it - values.begin()) << '\n';
if (it != values.end()) {
std::cout << "value=" << *it << '\n';
}
const auto end = std::upper_bound(values.begin(), values.end(), 7);
std::cout << "at_end=" << std::boolalpha << (end == values.end()) << '\n';
}
Result
index=4 value=4 at_end=true
The displayed code and declared result were verified in an isolated environment using the method recorded in the verification evidence for this exact version.