The C++ algorithm upper_bound function serves as a binary search variant. Its purpose is to provide an iterator that points to the initial element within the range [first, last) that exceeds the specified value val.
The initial iteration employs the < operator to evaluate the elements, while the subsequent iteration utilizes the designated comparison function, comp.
Syntax
default (1) template <class ForwardIterator, class T>
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,
const T& val);
custom (2) template <class ForwardIterator, class T, class Compare>
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,
const T& val, Compare comp);
Parameter
A forward iterator indicating the initial element within the range targeted for searching.
last: A forward iterator indicating the element following the last element in the range to be searched.
Define a custom binary predicate function named "comp" that takes two parameters and evaluates to true if the two arguments are arranged in a specific order, otherwise returning false. This function adheres to the strict weak ordering principle for sorting elements.
val : An upper limit value for comparing the elements within the specified range.
Return value
It yields an iterator that points to the initial element within the range that exceeds val or the last element if no matching element is located.
Complexity
On average, the complexity grows logarithmically with the span from the initial to the final element: executing a maximum of log2 (N) + 1 comparisons of elements where N = last - first.
Data races
The elements within the range [first, last) are retrieved.
Exceptions
This function will raise an exception if an exception is thrown during either element comparison or iterator operation.
Note: The invalid parameters cause an undefined behavior.
Example 1
Let's examine a straightforward example to showcase the application of the upper_bound function:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<int> v = {3, 1, 4, 6, 5};
decltype(v)::iterator it = upper_bound(v.begin(), v.end(), 3);
cout<<"Upper bound of 3 is: ";
cout << *it << endl;
return 0;
}
Output:
Upper bound of 3 is: 4
Example 2
Let's see another simple example:
#include <iostream> // std::cout
#include <algorithm> // std::lower_bound, std::upper_bound, std::sort
#include <vector> // std::vector
using namespace std;
int main () {
int myints[] = {10,20,30,30,20,10,10,20};
vector<int> v(myints,myints+8); // 10 20 30 30 20 10 10 20
sort (v.begin(), v.end()); // 10 10 10 20 20 20 30 30
vector<int>::iterator low,up;
low=lower_bound (v.begin(), v.end(), 20); // ^
up= upper_bound (v.begin(), v.end(), 20); // ^
cout << "lower_bound at position " << (low- v.begin()) << '\n';
cout << "upper_bound at position " << (up - v.begin()) << '\n';
return 0;
}
Output:
lower_bound at position 3
upper_bound at position 6
Example 3
Let's see another simple example:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int a[] = {2, 3, 5, 6, 7, 7, 7, 8, 9, 10};
vector<int> v(a, a+10);
cout <<"\nHere are the contents of v:\n";
for (vector<int>::size_type i=0; i<v.size(); i++)
cout <<v.at(i)<<" ";
vector<int>::iterator upper;
upper = upper_bound(v.begin(), v.end(), 3);
if (upper != v.end())
cout <<"\nUpper bound of 3 in v = "<<*upper;
upper = upper_bound(v.begin(), v.end(), 4);
if (upper != v.end())
cout <<"\nUpper bound of 4 in v = "<<*upper;
upper = upper_bound(v.begin(), v.end(), 5);
if (upper != v.end())
cout <<"\nUpper bound of 5 in v = "<<*upper;
upper = upper_bound(v.begin(), v.end(), 7);
if (upper != v.end())
cout <<"\nUpper bound of 7 in v = "<<*upper;
upper = upper_bound(v.begin(), v.end(), 0);
if (upper != v.end())
cout <<"\nUpper bound of 0 in v = "<<*upper;
upper = upper_bound(v.begin(), v.end(), 15);
if (upper != v.end())
cout <<"\nUpper bound of 15 in v = "<<*upper;
cout <<"\n\nNote that the upper bound location of 15 is \nthe end (one-past-the-last) vector position.";
return 0;
}
Output:
Here are the contents of v:
2 3 5 6 7 7 7 8 9 10
Upper bound of 3 in v = 5
Upper bound of 4 in v = 5
Upper bound of 5 in v = 6
Upper bound of 7 in v = 8
Upper bound of 0 in v = 2
Note that the upper bound location of 15 is
the end (one-past-the-last) vector position.
Example 4
Let's see another simple example:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool ignore_case(char a, char b) {
return(tolower(a) == tolower(b));
}
int main(void) {
vector<char> v = {'A', 'b', 'C', 'd', 'E'};
auto it = upper_bound(v.begin(), v.end(), 'C');
cout << "Upper bound of \'C\' is " << *it << endl;
it = upper_bound(v.begin(), v.end(), 'C', ignore_case);
cout << "Upper bound of \'C\' is " << *it << endl;
it = upper_bound(v.begin(), v.end(), 'z', ignore_case);
cout << "All elements are less than \'z\'." << endl;
return 0;
}
Output:
Upper bound of 'C' is d
Upper bound of 'C' is C
All elements are less than 'z'.
