CKTIS / C++
std::lower_bound — first position not less than a key
std::lower_bound searches a suitably partitioned range for its boundary: the first element not less than the key, or the end of the range. It returns an iterator, not confirmation that an equal value exists.
Version: C++23; repository compiler flag, production runtime not attested
Syntax
#include <algorithm>
std::lower_bound(first, last, value)
std::lower_bound(first, last, value, comp)std::lower_bound, declared in <algorithm>, searches [first, last) and returns the first iterator for which comp(*it, value) is false, or last if no such element exists. Without comp, it uses the default less-than comparison. In an ascending numeric range, the result points to the first element >= value, including the first duplicate.
The precondition is partitioning for the particular key: all elements satisfying comp(element, value) must precede all remaining elements. Full sorting under the same comparison is sufficient but not necessary. Violating this condition causes undefined behavior; the function does not sort the data.
The result does not confirm that the key exists. Check it != last before using *it. In the integer example, the code checks only it != values.end() before printing the candidate value; it does not compare that value with the key. To check equality, you can test *it == key separately after ruling out the end of the range. For a custom ordering, equivalence means !comp(a, b) && !comp(b, a), not necessarily a == b.
At least forward iterators are required. For N elements, the comparison count is O(log N), but without random-access iterators the number of iterator steps can be linear. The example targets C++23; the linked document is an evolving working draft, not a frozen C++23 edition.
Examples
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
const std::vector<int> values{1, 3, 3, 7};
for (int key : {3, 4, 9}) {
const auto it = std::lower_bound(values.begin(), values.end(), key);
std::cout << key << ": index=" << (it - values.begin());
if (it != values.end()) {
std::cout << ", value=" << *it;
} else {
std::cout << ", end";
}
std::cout << '\n';
}
}
Result
3: index=1, value=3 4: index=3, value=7 9: index=4, end
The displayed code and declared result were verified in an isolated environment using the method recorded in the verification evidence for this exact version.