CppHow-ToBeginner · 3 min read

How to Use lower_bound and upper_bound in C++

In C++, lower_bound returns an iterator to the first element not less than a given value, while upper_bound returns an iterator to the first element greater than that value. Both require the container to be sorted and are used to find insertion points or count occurrences efficiently.

📐

Syntax

lower_bound and upper_bound are functions in the <algorithm> header. They are used like this:

auto it = std::lower_bound(begin, end, value);
auto it = std::upper_bound(begin, end, value);

Here, begin and end are iterators to the start and end of a sorted range, and value is the element to compare.

lower_bound finds the first position where value could be inserted without breaking order (first element ≥ value).

upper_bound finds the first position where value would go after all equal elements (first element > value).

cpp

#include <algorithm>
#include <vector>

int main() {
    std::vector<int> v = {1, 3, 3, 5, 7};
    auto lb = std::lower_bound(v.begin(), v.end(), 3); // points to first 3
    auto ub = std::upper_bound(v.begin(), v.end(), 3); // points to 5
    return 0;
}

💻

Example

This example shows how to find the range of a value in a sorted vector using lower_bound and upper_bound. It prints the positions and counts how many times the value appears.

cpp

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> data = {1, 2, 4, 4, 4, 5, 7};
    int value = 4;

    auto lower = std::lower_bound(data.begin(), data.end(), value);
    auto upper = std::upper_bound(data.begin(), data.end(), value);

    if (lower != data.end()) {
        std::cout << "Lower bound at index: " << (lower - data.begin()) << "\n";
        std::cout << "Upper bound at index: " << (upper - data.begin()) << "\n";
        std::cout << "Count of " << value << ": " << (upper - lower) << "\n";
    } else {
        std::cout << value << " not found in data.\n";
    }

    return 0;
}

Output

Lower bound at index: 2 Upper bound at index: 5 Count of 4: 3

⚠️

Common Pitfalls

Common mistakes when using lower_bound and upper_bound include:

Using them on unsorted containers, which leads to incorrect results.
Confusing lower_bound and upper_bound roles.
Not checking if the returned iterator is end() before dereferencing.

Always ensure the container is sorted before calling these functions.

cpp

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> unsorted = {5, 1, 3, 4};
    int val = 3;

    // Wrong: container not sorted
    auto lb_wrong = std::lower_bound(unsorted.begin(), unsorted.end(), val);
    std::cout << "Wrong lower_bound points to: " << (lb_wrong != unsorted.end() ? std::to_string(*lb_wrong) : "end") << "\n";

    // Correct: sort first
    std::sort(unsorted.begin(), unsorted.end());
    auto lb_right = std::lower_bound(unsorted.begin(), unsorted.end(), val);
    std::cout << "Correct lower_bound points to: " << (lb_right != unsorted.end() ? std::to_string(*lb_right) : "end") << "\n";

    return 0;
}

Output

Wrong lower_bound points to: 5 Correct lower_bound points to: 3

📊

Quick Reference

Function	Returns	Condition	Use Case
lower_bound(begin, end, val)	Iterator to first element ≥ val	Container sorted ascending	Find insertion point or first occurrence
upper_bound(begin, end, val)	Iterator to first element > val	Container sorted ascending	Find insertion point after last occurrence

✅

Key Takeaways

Use lower_bound to find the first position where a value can be inserted without breaking order.

Use upper_bound to find the position just after the last occurrence of a value.

Both functions require the container to be sorted before use.

Check if the returned iterator is not end() before dereferencing.

They help efficiently count occurrences or insert elements in sorted containers.