What is the upper_bound() method in C++?
The upper_bound() function is used to find the first element in the range [start, end) whose value is greater than the val and returns an iterator pointing to that value. If no such value exists, then it returns an iterator to the index end + 1. Internally, this function implements a binary search algorithm to find the iterator.
Parameters
This function accepts the following parameters:
-
start: This parameter specifies the start index of the array or vector where you want to search. -
end: This parameter specifies the end index of the array or vector where you want to search. -
value: This is the value that you want to search for. -
comp: This is an optional parameter that is used to compare the values in the array. This can be used if we want to compare the values in a custom way.
Return
The upper_bound() function returns an iterator that points to the first value that is greater than the specified value, or returns the iterator pointing to the (end + 1) index if no such element is found.
Let’s look at the code now:
#include <iostream>#include <algorithm>using namespace std;int main() {vector<int> vec = {10,10,10,20,20,20,30,30,40,40,40};auto it = upper_bound(vec.begin(), vec.end(), 20);cout << "The index is " << (it - vec.begin());return 0;}
Explanation:
-
In lines 1 and 2, we import the required package.
-
In line 6, we define the vector with some integer elements.
-
In line 7, we call the function
upper_bound()and pass the parameters. We want to search for “20” in the vector. -
In line 8, we print the index of the element that is greater than 20. Remember that we get an iterator from the
upper_bound()function, so to get the index, we need to subtract it from thevec.begin()iterator. -
We can see that it returns the index 6, which means the element at index 6 is greater than the specified value, i.e., 20. Also, all the elements after the index 6 are greater than 20.
To summarize, this function can be used to find the last occurrence of an element in an array.