# Binary search in sorted vector of pairs in C++

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
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
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 !!