# lower_bound() and upper_bound() in Vector of Pairs in C++

Hi folks! In this tutorial, we are going to learn and implement lower_bound () and upper_bound() in the vector of pairs in C++. Before moving forward let’s have a look at what is vector of pairs.

**What is Vector of Pairs?**

A pair is considered as a container that holds two numbers mapping to each other, and a vector containing such pairs is called a vector of pair.

Now now lets further proceed with the lower_bound() and upper_bound().

## lower_bound()

Lower bound for vector pairs(a,b) will return an iterator whose first element will be greater or equal to a and second value b is greater than or equal to b. If the case is not fulfilled iterator will return a value whose pairs are not present in the pairs of vectors.

In short we can say that it returns first element which is ≥value. If not, return end().

### Algorithm

- Write a function lower_bound() to implement lower bound in code.
- Add auto iterator which helps to point the lower_bound() of given pair.
- Insert sorted pairs of vectors in driver code.
- Mention the pairs for which lower_bound() needs to be searched.
- Call the function lower_bound() to find the lower bond pairs in given vectors.
- Index of lower bound will be obtained.

### C++Code: For lower_bound() in vector of pairs

Read the comments in the code for better understanding.

#include <bits/stdc++.h> using namespace std; // This Function helps to implement lower_bound() void findLowerBound(vector<pair<int, int> >& arr, pair<int, int>& p) { // This iterator helps to initilize lower bound. auto low = lower_bound(arr.begin(), arr.end(), p); cout << "lower_bound() for {1, 3}" << " is at index: " << low - arr.begin() << endl; } //Driver code starts int main() { //sorted pair of vector pairs are inserted. vector<pair<int, int> > arr; arr = { { 1, 1 }, { 1, 2 }, { 1, 3 }, { 2, 1 }, { 2, 2 }, { 2, 3 } }; // Given pair {1, 3} pair<int, int> p = { 1, 3 }; //Function to call lower bound findLowerBound(arr, p); return 0; }

Output:

lower_bound() for {1, 3} is at index: 2

## upper_bound()

Upper bound for vector pairs (a,b) will return an iterator whose first value is greater than a and second value will be greater than b. If the case is not fulfilled iterator returns to pair of vectors that are not present in pair of vectors.

In short we can say that it returns first element which is >value. If not, return end().

### Working Algorithm

- Write a function upper_bound() to implement upper bound in code.
- Add auto iterator which helps to point the upper_bound() of given pair.
- Insert sorted pairs of vectors in driver code.
- Mention the pairs for which upper_bound() needs to be searched.
- Call the function upper_bound() to find the upper bond pairs in given vectors.
- Index of upper bound will be obtained.

### C++ Code: For upper_bound() in vector of pairs

Read the comments in the code for better understanding.

#include <bits/stdc++.h> using namespace std; // This function is used to implement upper_bound() void findUpperBound(vector<pair<int, int> >& arr, pair<int, int>& p) { // This iterator will point to the upper bond() of the pair auto up = upper_bound(arr.begin(), arr.end(), p); cout << "upper_bound() for {1, 3}" << " is present at index: " << up - arr.begin() << endl; } int main() { // This is sorted vector of Pairs vector<pair<int, int> > arr; arr = { { 1, 1 }, { 1, 2}, { 1, 3 }, { 2, 1 }, { 2,2 }, { 2, 3 } }; // Given pair {1,3} whose index is to be found. pair<int, int> p = { 1, 3 }; // This function calls the upper bound pairs of vector findUpperBound(arr, p); return 0; }

Output:

upper_bound() for {1, 3} is present at index: 3

I hope, this tutorial will be helpful for you.

in upper bound of {1,3} ,mentioned answer is {2,1} ie. index 3 ;

But as you have define above that it returns the iterator that fulfill the condition:

first value as well as second value should be greater.

But here only upper bound is found on the basis of first element only.

Correct me if i am wrong. Thanks!!

Yes same doubt.

I think it only finds the first element that is greater

I think there should be “or” because if first element is equal then it will check for second element. example-> if {1,4} is also in arr, then up will be storing the pointer to it.

As {1,4} is not present, or any other element whose first is 1 and second greater than 3, so it will jump to {2,1} whose first element is greater than first element of {1,3}.