upper_bound in C++ - GeeksforGeeks (2024)

upper_bound() is a standard library function in C++ defined in the header. It returns an iterator pointing to the first element in the range [first, last] that is greater than value, or last if no such element is found. The elements in the range shall already be sorted or at least partitioned with respect to val.

Syntax of upper_bound()

The upper bound function have multiple signatures to fulfil the programmer’s requirements:

upper_bound (first, last, val);
upper_bound (first, last, val, comp);

Parameters

• first, last: The range used is [first, last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
• val: Value of the upper bound to search for in the range.
• comp: Binary function that accepts two arguments (the first of the type pointed by ForwardIterator, and the second, always val), and returns a value convertible to bool. The function shall not modify any of its arguments. This can either be a function pointer or a function object.

Return Value

An iterator to the upper bound of val in the range. If all the element in the range compare less than val, the function returns last.

Examples of upper_bound()

Input:
10 20 30 30 40 50
Output:
upper_bound for element 30 is at index 4
Input:
10 20 30 40 50
Output: 
upper_bound for element 45 is at index 4
Input:
10 20 30 40 50
Output:
upper_bound for element 60 is at index 5

Below are some C++ programs to illustrate the use of std::upper_bound:

Example 1: Program to demonstrate the basic use of std::upper_bound.

// CPP program to illustrate using// std :: upper_bound with vectors#include <bits/stdc++.h>using namespace std;// Driver codeint main(){ vector<int> v{ 10, 20, 30, 40, 50 }; // Print vector cout << "Vector contains :"; for (int i = 0; i < v.size(); i++) cout << " " << v[i]; cout << "\n"; vector<int>::iterator upper1, upper2; // std :: upper_bound upper1 = upper_bound(v.begin(), v.end(), 35); upper2 = upper_bound(v.begin(), v.end(), 45); cout << "\nupper_bound for element 35 is at position : " << (upper1 - v.begin()); cout << "\nupper_bound for element 45 is at position : " << (upper2 - v.begin()); return 0;}

Vector contains : 10 20 30 40 50upper_bound for element 35 is at position : 3upper_bound for element 45 is at position : 4

Example 2: Program to show the working of std::upper_bound with Arrays

// CPP program to illustrate using// std :: upper_bound with arrays#include <bits/stdc++.h>using namespace std;// Main Functionint main(){ int arr[] = { 10, 20, 30, 40, 50 }; // Print elements of array cout << "Array contains :"; for (int i = 0; i < 5; i++) cout << " " << arr[i]; cout << "\n"; // using upper_bound int upper1 = upper_bound(arr, arr + 5, 35) - arr; int upper2 = upper_bound(arr, arr + 5, 45) - arr; cout << "\nupper_bound for element 35 is at position : " << (upper1); cout << "\nupper_bound for element 45 is at position : " << (upper2); return 0;}

Array contains : 10 20 30 40 50upper_bound for element 35 is at position : 3upper_bound for element 45 is at position : 4

Time Complexity: O (log₂(last – first)), as the number of comparisons performed is logarithmic in the distance between first and last.
Auxiliary Space: O(1)

How upper_bound Works?

The upper_bound function uses a binary search algorithm to find the first element that is greater than the given value. Here’s a simplified version of how it works:

1. The range [first, last) is divided in half.
2. The middle element is compared to the value.
3. If the middle element is less than or equal to value, the search continues in the right half.
4. If the middle element is greater than value, the search continues in the left half.
5. The process repeats until the range is empty.

Frequently Asked Questions (FAQs) on C++ upper_bound()

1. What is the difference between upper_bound and lower_bound?

• upper_bound returns an iterator to the first element greater than the given value.
• lower_bound returns an iterator to the first element not less than (i.e., greater than or equal to) the given value.

2. Can upper_bound be used with non-sorted ranges?

No, upper_bound requires the range to be sorted. Using it on non-sorted ranges results in undefined behavior.

3. How does upper_bound handle duplicates?

upper_bound returns an iterator to the first element that is greater than the given value, skipping over any duplicates.