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

  1. Write a function lower_bound() to implement lower bound in code.
  2. Add auto iterator which helps to point the lower_bound() of given pair.
  3. Insert sorted pairs of vectors in driver code.
  4. Mention the pairs for which lower_bound() needs to be searched.
  5. Call the function lower_bound() to find the lower bond pairs in given vectors.
  6. 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

  1. Write a function upper_bound() to implement upper bound in code.
  2. Add auto iterator which helps to point the upper_bound() of given pair.
  3. Insert sorted pairs of vectors in driver code.
  4. Mention the pairs for which upper_bound() needs to be searched.
  5. Call the function upper_bound() to find the upper bond pairs in given vectors.
  6. 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.

Leave a Reply

Your email address will not be published.