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 log2n operations. Here, n is the size of the input array.
Time Complexity: O(log2(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:
Leave a Reply