std::upper_bound() function with example in C++ STL

In this article, we are going to learn about the usage of the library function upper_bound() and how to use that?
Submitted by Radib Kar, on August 13, 2020

std::upper_bound()

std::upper_bound() is an STL library function, which comes under the algorithm header library and finds the upper bound of the searching element in a range. Upper bound means the next greater element in the sorted range for the searching element.

Say the range is: [4, 5, 6, 9, 12] and the searching element is 6, then the upper bound is 9 itself. If the searching element is 7 then the upper bound will again be 9.

Cases:

When a searching element exists:
std::upper_bound() returns an iterator to the next greater element of the searching element
When searching element doesn't exist:
1. If all elements are greater than the searching element:
  upper_bound() returns an iterator to begin of the range.
2. If all elements are lower than the searching element:
  upper_bound() returns an iterator to end of the range( No upper bound exists).
3. Otherwise,
  upper_bound() returns an iterator to the next greater element to the search element (The closest element greater than the search element) of the range.

To use the upper_bound() the range needs to be sorted.

Syntax:

ForwardIterator upper_bound(
    ForwardIterator first, 
    ForwardIterator last, 
    const T& searching_element
    );

Parameter(s):

ForwardIterator first: iterator to the start of the range
ForwardIterator last: iterator to the end of the range
const T& searching_element: T is the data type and searching_element is the element which upper bound is to be found

Return Type: The return type is an iterator to the upper bound found in the range.

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

int main()
{
    vector<int> arr{ 6, 5, 9, 12, 4 };
 
    //sort before using upper_bound()
    sort(arr.begin(), arr.end());

    int searching_element = 6;
    vector<int>::iterator it;
    it = upper_bound(arr.begin(), arr.end(), searching_element);
    
    //if all elements are smaller than the searching 
    //element then no upper bound exists
    if (it == arr.end()) {
        cout << "No upper bound exists\n";
    }
    else
        cout << "Upperr bound of " << searching_element << ": " << *it << endl;

    searching_element = 7;

    it = upper_bound(arr.begin(), arr.end(), searching_element);
    
    //if all eleemnts are smaller than the searching 
    //element then no upper bound exists
    if (it == arr.end()) {
        cout << "No upper bound exists\n";
    }
    else
        cout << "Upper bound of " << searching_element << ": " << *it << endl;

    return 0;
}

Output:

Upperr bound of 6: 9
Upper bound of 7: 9

In the above upper_bound() function, to compare between elements default comparator operator '<' is used.

But we have an extended version function which uses a user-defined comparator to compare b/w elements.

ForwardIterator upper_bound(
    ForwardIterator first, 
    ForwardIterator last, 
    const T& searching_element, 
    Comparator comp
    );

Parameter(s):

ForwardIterator first: iterator to the start of the range
ForwardIterator last: iterator to the end of the range
const T& searching_element: T is the data type and searching_element is the element which upper bound is to be found
Comparator comp: user-defined comparator

Return type: The return type is an iterator to the upper bound found in the range.

This can be helpful if you have user-defined data types.