Knowledge baseExam Center
ENEnglish
Choose language13

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.

Sources