upper_bound() in C++

In this tute, we will discuss std::upper_bound() in C++.

There are many ways to find the next greater element of a value in a sorted array. The first method is to run a linear loop to find the first value greater than the given value. The second method would be to do a binary search. But it wouldn’t be feasible to code for all the data structures. The std::upper_bound() can be used for a variety of data structures.

 

The std::upper_bound() is a method in the Standard Template Library(STL) in C++. It returns an iterator pointing to the next grater value in the range [first, last). If no such element is found it returns the pointer pointing to the last. Most importantly, elements in the range [first, last) must be sorted. Remember that, the range [1, 5) contains 1, 2, 3, 4 only.

 

std::upper_bound() in C++:

ForwardIterator upper_bound(ForwardIterator first, ForwardIterator Last, const T& val);
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator Last, const T& val,
                                                                         Compare comp);

The first and last iterators point to the first and last positions in the range [first, last). The val is the value to which the upper bound is to be found. The comp is a boolean function that is used to say whether the elements in the range are sorted in ascending or descending order.

 

Let’s see a few examples:

upperbound of 3 in array [1, 2, 3, 4, 5] points to index 3 (value 4).
upperbound of 3 in array [1, 2, 3, 3, 5] points to index 4 (value 5).
upperbound of 5 in array [1, 2, 3, 3, 5] points to end of the array (not the index 4).

 

upper_bound() for non-decreasing arrays:

Let’s jump into the code right away.

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

int main()
{
    int n, i, x;

    n = 6;
    vector<int> ar = {10, 20, 30, 30, 40, 50};

    sort(ar.begin(), ar.end());

    cout<<"Array contains: ";
    for(i=0 ; i<n ; ++i)
        cout<<ar[i]<<' ';
    cout<<endl;

    vector<int>::iterator it1 = upper_bound(ar.begin(), ar.end(), 5);
    cout<<"upper_bound(5):"<<endl;
    cout<<"Index: "<<(it1 - ar.begin())<<endl;
    cout<<"Value: "<<*it1<<endl;
    cout<<"isEnd: "<<(it1 == ar.end())<<endl;
    cout<<endl;
    
    vector<int>::iterator it2 = upper_bound(ar.begin(), ar.end(), 30);
    cout<<"upper_bound(30):"<<endl;
    cout<<"Index: "<<(it2 - ar.begin())<<endl;
    cout<<"Value: "<<*it2<<endl;
    cout<<"isEnd: "<<(it2 == ar.end())<<endl;
    cout<<endl;

    vector<int>::iterator it3 = upper_bound(ar.begin(), ar.end(), 50);
    cout<<"upper_bound(50):"<<endl;
    cout<<"Index: "<<(it3 - ar.begin())<<endl;
    cout<<"Value: "<<*it3<<endl;
    cout<<"isEnd: "<<(it3 == ar.end())<<endl;

    return 0;
}

Output:

Array contains: 10 20 30 30 40 50 
upper_bound(5):
Index: 0
Value: 10
isEnd: 0

upper_bound(30):
Index: 4
Value: 40
isEnd: 0

upper_bound(50):
Index: 6
Value: 1267950072
isEnd: 1

For non-increasing arrays:

Let’s see what happens when we use the same function and then compare it with using the compare function.

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

int main()
{
    int n, i, x;

    n = 6;
    vector<int> ar = {10, 20, 30, 30, 40, 50};
    
    sort(ar.begin(), ar.end(), greater<int>());
    
    cout<<"Array contains: ";
    for(i=0 ; i<n ; ++i)
        cout<<ar[i]<<' ';
    cout<<endl;

    vector<int>::iterator it1 = upper_bound(ar.begin(), ar.end(), 30);
    cout<<"upper_bound(30) without comp:"<<endl;
    cout<<"Index: "<<(it1 - ar.begin())<<endl;
    cout<<"Value: "<<*it1<<endl;
    cout<<"isEnd: "<<(it1 == ar.end())<<endl;
    cout<<endl;

    vector<int>::iterator it2 = upper_bound(ar.begin(), ar.end(), 60, greater<int>());
    cout<<"upper_bound(60) with comp:"<<endl;
    cout<<"Index: "<<(it2 - ar.begin())<<endl;
    cout<<"Value: "<<*it2<<endl;
    cout<<"isEnd: "<<(it2 == ar.end())<<endl;
    cout<<endl;

    vector<int>::iterator it3 = upper_bound(ar.begin(), ar.end(), 30, greater<int>());
    cout<<"upper_bound(30) with comp:"<<endl;
    cout<<"Index: "<<(it3 - ar.begin())<<endl;
    cout<<"Value: "<<*it3<<endl;
    cout<<"isEnd: "<<(it3 == ar.end())<<endl;
    cout<<endl;

    vector<int>::iterator it4 = upper_bound(ar.begin(), ar.end(), 10, greater<int>());
    cout<<"upper_bound(10) with comp:"<<endl;
    cout<<"Index: "<<(it4 - ar.begin())<<endl;
    cout<<"Value: "<<*it4<<endl;
    cout<<"isEnd: "<<(it4 == ar.end())<<endl;

    return 0;
}

Output:

Array contains: 50 40 30 30 20 10 
upper_bound(30) without comp:
Index: 6
Value: -57410614
isEnd: 1

upper_bound(60) with comp:
Index: 0
Value: 50
isEnd: 0

upper_bound(30) with comp:
Index: 4
Value: 20
isEnd: 0

upper_bound(10) with comp:
Index: 6
Value: -57410614
isEnd: 1

Time Complexity:

Since the array is sorted, the element is searched in at most log₂n operations. Here, n is the size of the input array.

Time Complexity: O(log₂(last – first))

 

Finally, If you have any queries or doubts related to std::upper_bound() in C++, simply comment in the comment section provided below.

Also, read:

• Segment tree in C++
• C++ program to detect integer overflow