Binary search in sorted vector of pairs in C++

By Dinesh Kumar

In this tutorial, we are going to see binary search in sorted vector of pairs in C++. Here we will learn about the vector of pairs, binary search for sorted vector of pairs and after that, we will see the C++ program for the same.

Vector of pairs

A vector that contains pairs as their elements is known as a vector of pairs.
For example:-
vec={ {1,2}, {3,5}, {6,4}, {8,9}, {5,1} };
Let us see the code for this:-

#include<bits/stdc++.h>
using namespace std;

int main () 
{
  //Initializing vector of pairs
   vector<pair<int,int>>vect;
   //Inserting values in vector
   vect.push_back(make_pair(1, 2)); 
   vect.push_back(make_pair(3, 7)); 
   vect.push_back(make_pair(4, 1)); 
   vect.push_back(make_pair(23, 8)); 
   vect.push_back(make_pair(74, 30)); 
   vect.push_back(make_pair(90, 24)); 
   vect.push_back(make_pair(32, 21));

   //Displaying vector of pairs
   for(auto x:vect)
   		cout<<x.first<<"-"<<x.second<<endl;

   return 0;
}

Output:-

1-2
3-7
4-1
23-8
74-30
90-24
32-21

Binary search in sorted vector of pairs

Case 1: Search for a pair in a sorted vector of pairs

We can search a pair in a sorted vector of pairs by using the built-in function “binary_search()”of STL library.
Syntax of the function:-

binary_search(start_address, end_address, value_to_find);

Let us move to the C++ code:-

#include<bits/stdc++.h>
using namespace std;

int main () 
{
  //Initializing vector of pairs
  vector<pair<int,int>>vect;
  //Initializing pair to search
  pair<int,int>mypair{74,30};
   	//Inserting values in vector
   	vect.push_back(make_pair(1, 2)); 
   	vect.push_back(make_pair(3, 7)); 
   	vect.push_back(make_pair(4, 1)); 
   	vect.push_back(make_pair(23, 8)); 
   	vect.push_back(make_pair(74, 30)); 
   	vect.push_back(make_pair(90, 24)); 
   	vect.push_back(make_pair(32, 21));

   	//Displaying vector of pairs
        cout<<"Given vector of pairs is:"<<endl;
   	for(auto x:vect)
   		cout<<x.first<<"-"<<x.second<<endl;

   	//Sorting vector of pairs
   	sort(vect.begin(),vect.end());

   	//Binary search for pair (74,30)
   	if(binary_search(vect.begin(),vect.end(),mypair))
   		cout<<"Pair found"<<endl;
   	else
   		cout<<"Pair not found"<<endl;
   return 0;
}

Output:-

1-2
3-7
4-1
23-8
74-30
90-24
32-21
Pair found

Case 2: Search for first element of pair in a sorted vector of pairs

We can search a first element of a pair in a sorted vector of pairs by using the built-in function “binary_search()”of the STL library. We modify the binary_search() function and we pass a fourth argument, a call to a user-defined explicit function in the binary_search() function. This function compares the searching value with the first element of pairs present in vectors of pair.
Let us move to the C++ code:-

#include<bits/stdc++.h>
using namespace std;


//Function that compare first element of pair with n
struct comp { 
    int operator()(const pair<int,int>&mypair,const int& n) 
    { 
        if(mypair.first < n)
        	return 1;
        return 0;
    } 
    int operator()(const int& n,const pair<int,int>& mypair) 
    { 
        if(n < mypair.first)
        	return 1;
        return 0;
    } 
}; 


int main () 
{
  //Initializing vector of pairs
  vector<pair<int,int>>vect;
  //Initializing value to search
  int n=74;
   	//Inserting values in vector
   	vect.push_back(make_pair(1, 2)); 
   	vect.push_back(make_pair(3, 7)); 
   	vect.push_back(make_pair(4, 1)); 
   	vect.push_back(make_pair(23, 8)); 
   	vect.push_back(make_pair(74, 30)); 
   	vect.push_back(make_pair(90, 24)); 
   	vect.push_back(make_pair(32, 21));

   	//Displaying vector of pairs
        cout<<"Given vector of pairs is:"<<endl;
   	for(auto x:vect)
   		cout<<x.first<<"-"<<x.second<<endl;

   	//Sorting vector of pairs
   	sort(vect.begin(),vect.end());

   	//Binary search for value n=74
   	//comp function is passed as argument for comparsion
   	if(binary_search(vect.begin(),vect.end(),n,comp()))
   		cout<<"Value found"<<endl;
   	else
   		cout<<"Value not found"<<endl;
   return 0;
}

Output:-

1-2
3-7
4-1
23-8
74-30
90-24
32-21
Value found

 Thanks for reading this tutorial. I hope it helps you !!