How to Use upper_bound in C++: Syntax and Examples

In C++, upper_bound is a standard library function that returns an iterator pointing to the first element in a sorted range that is greater than a specified value. You use it by including <algorithm> and calling std::upper_bound(begin, end, value) on a sorted container or array.

Syntax

The basic syntax of upper_bound is:

• std::upper_bound(begin, end, value)
• begin and end define the sorted range to search.
• value is the value to compare against.
• It returns an iterator to the first element greater than value.

cpp

template<class ForwardIt, class T>
ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value);

Example

This example shows how to use upper_bound to find the position of the first element greater than 5 in a sorted vector.

cpp

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

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

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

    if (it != data.end()) {
        std::cout << "First element greater than " << value << " is " << *it << " at index " << (it - data.begin()) << "\n";
    } else {
        std::cout << "No element greater than " << value << " found.\n";
    }

    return 0;
}

Output

First element greater than 5 is 7 at index 4

Common Pitfalls

Common mistakes when using upper_bound include:

• Using upper_bound on an unsorted range, which leads to undefined behavior.
• Confusing upper_bound with lower_bound: upper_bound finds the first element greater than the value, while lower_bound finds the first element not less than the value.
• Not checking if the returned iterator is end() before dereferencing it.

cpp

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

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

    // Wrong: upper_bound on unsorted vector
    auto it_wrong = std::upper_bound(unsorted.begin(), unsorted.end(), value);
    std::cout << "Result on unsorted vector (undefined behavior): " << (it_wrong != unsorted.end() ? std::to_string(*it_wrong) : "end") << "\n";

    // Right: sort first
    std::sort(unsorted.begin(), unsorted.end());
    auto it_right = std::upper_bound(unsorted.begin(), unsorted.end(), value);
    std::cout << "Result after sorting: " << (it_right != unsorted.end() ? std::to_string(*it_right) : "end") << "\n";

    return 0;
}

Output

Result on unsorted vector (undefined behavior): 7
Result after sorting: 5

Quick Reference

upper_bound Cheat Sheet:

• Requires sorted range.
• Returns iterator to first element > value.
• Use lower_bound to find first element ≥ value.
• Include <algorithm> header.
• Works with arrays, vectors, and other containers with iterators.

Key Takeaways

Use std::upper_bound on sorted ranges to find the first element greater than a given value.

Always include and pass begin and end iterators of the sorted container.

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

upper_bound differs from lower_bound by strictly finding elements greater than the value.

Using upper_bound on unsorted data causes undefined behavior.