Implementation of lower_bound() and upper_bound() in Array of Pairs in C++
In this article we will discuss the implementation of the lower_bound() and upper_bound() in an array of pairs.
- lower_bound(): It returns an iterator pointing to the first element in the range [first, last) which has a value greater than or equals to the given value “val”. But in Array of Pairs lower_bound() for pair(x, y) will return an iterator pointing to the position of pair whose the first value is greater than or equals x and second value is greater than equals to y.
If the above-mentioned criteria are not met, then it returns an iterator to the index which out of the array of pairs. - upper_bound(): It returns an iterator pointing to the first element in the range [first, last) which has a value greater than the given value “val”. But in Array of Pairs upper_bound() for pair(x, y) will return an iterator pointing to the position of pair whose the first value is greater than x and second value is greater than y.
If the above-mentioned criteria are not met, then it returns an iterator to the index which out of the array of pairs.
Syntax:
// For lower bound
lower_bound(array_name, array_name + array_size, value, comparator_function);// For upper bound
upper_bound(array_name, array_name + array_size, value, comparator_function);
Parameters: The function lower_bound() and upper_bound() in array of pairs accepts the following parameters:
- array_name & array_size: The name and size of the array which represents the interval between [start, end).
- value: Value of the lower_bound()/upper_bound() to be searched in the range.
- comparator_function: Binary function that accepts two arguments as its input, namely an element of type pair from the array, and the second is the value for which lower_bound()/upper_bound() has to be found and returns a boolean value.
Return Type: It returns an iterator pointing to the first element of the array whose first parameter is greater than or equal to the value.
Below is the program to demonstrate lower_bound() and upper_bound() in array of pairs:
C++
// C++ program to demonstrate lower_bound() // and upper_bound() in Array of Pairs #include <bits/stdc++.h> using namespace std; // Function to implement lower_bound() void findLowerBound(pair< int , int > arr[], pair< int , int >& p, int n) { // Given iterator points to the // lower_bound() of given pair auto low = lower_bound(arr, arr + n, p); cout << "lower_bound() for {2, 5}" << " is at index: " << low - arr << endl; } // Function to implement upper_bound() void findUpperBound(pair< int , int > arr[], pair< int , int >& p, int n) { // Given iterator points to the // lower_bound() of given pair auto up = upper_bound(arr, arr + n, p); cout << "upper_bound() for {2, 5}" << " is at index: " << up - arr << endl; } // Driver Code int main() { // Given sorted array of Pairs pair< int , int > arr[] = { { 1, 3 }, { 1, 7 }, { 2, 4 }, { 2, 5 }, { 3, 8 }, { 8, 6 } }; // Given pair {2, 5} pair< int , int > p = { 2, 5 }; // Size of array int n = sizeof (arr) / sizeof (arr[0]); // Function Call to find lower_bound // of pair p in arr findLowerBound(arr, p, n); // Function Call to find upper_bound // of pair p in arr findUpperBound(arr, p, n); return 0; } |
Output:
lower_bound() for {2, 5} is at index: 3 upper_bound() for {2, 5} is at index: 4
Contact Us