## Introduction

An array is one of the first friends that we make when we start our journey in programming. In our every up and down, the array was our good helper, but as we had driven deep into the concept of programming, let us introduce you to an evolved form of array, ‘**vector**.’ Vectors are similar to dynamic arrays in that they can resize themselves automatically when an element is added or removed.

This article will look at binary search in sorted vector of pairs in C++. We will learn about the vector of pairs, binary search for sorted vector of pairs, and the C++ program. So let’s get started!

### Problem Statement

We are given sorted vector pairs, i.e., a list of elements just like an array, where we need to find a particular element using a binary search.

Before doing a binary search in the sorted vector of pairs, we will first see what vector of pairs are.

### Vector of pairs

A vector of pairs is a vector that contains pairs as its elements.

**Example**: vec={ {1,2}, {3,6}, {7,4}, {10,15}, {5,2}, {87,21}, {29,18} };

### Sample Example

**Example 1:**

**Input**:

`vec={ {1,2}, {6, 4}, {3,4}, {6,1} }; n = 3`

**Output**:

```
Given vector of pairs is:
1-2
6-4
3-4
6-1
Value exists in a vector
```

**Example 2:**

**Input**:

`vec={ {4,8}, {6, 4}, {1,4}, {2,8} }; n = 9`

**Output**:

```
Given vector of pairs is:
4-8
6-4
1-4
2-8
Value does not exist
```

### Algorithm

- Initializing vector of pairs.
- Insert value in vectors.
- Displaying the values of vectors.
- End.

### Implementation

Let’s have a look at the code for this:

```
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
int main ()
{
//Initializing vector of pairs
vector<pair<int,int>>vect;
//Inserting values in vector
vect.pb(make_pair(1, 2));
vect.pb(make_pair(3, 6));
vect.pb(make_pair(7, 4));
vect.pb(make_pair(10, 15));
vect.pb(make_pair(5, 2));
vect.pb(make_pair(87, 21));
vect.pb(make_pair(29, 18));
//Displaying vector of pairs
for(auto x:vect)
cout<<x.first<<"-"<<x.second<<endl;
return 0;
}
```

**Output:**

## Search for a key in a sorted vector of pairs

We are using the **STL library's **built-in function "binary search()" to find the element in a sorted vector of pairs. In the binary search() function, we modify it and pass a fourth argument, a call to a user-defined explicit function. This function compares the searching value to the first element of pairs found in pair vectors.

### Pseudocode

```
Declare a structure keycompare
Function operator()(const pair& v, const int& k)
returns Booleans.
status = v.first < k.
return status
Function operator()(const pair& v, const int& k)
returns Booleans.
status = k < v.first.
return status
declare a vector v.
declare the key and value pair within v of the integer datatype
now call push_back() function to insert values in v vector.
vect.push_back(make_pair(1, 2));
vect.push_back(make_pair(3, 6));
vect.push_back(make_pair(7, 4));
vect.push_back(make_pair(10, 15));
vect.push_back(make_pair(5, 2));
vect.push_back(make_pair(87, 21));
vect.push_back(make_pair(29, 18));
afterward call sort() function to sort all elements of the vector v.
print “Given vector of pair is”.
print “Key” “Value”
for (pair& n : v)
now print the first and second value of n.
if (binary_search(v.begin(), v.end(), 74,keycompare()))
print “value exists in vector”
else
Print “value does not exist”.
End.
```

### Implementation

```
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
//Function that compare first element of pair with n
struct keycompare{
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.pb(make_pair(1, 2));
vect.pb(make_pair(3, 6));
vect.pb(make_pair(7, 4));
vect.pb(make_pair(10, 15));
vect.pb(make_pair(5, 2));
vect.pb(make_pair(87, 21));
vect.pb(make_pair(29, 18));
//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 exist in vector"<<endl;
else
cout<<"Value does not exist"<<endl;
return 0;
}
```

**Output:**

#### Time complexity

The time complexity of this approach is** O(n*logN), **as we are using binary sort here.

#### Space complexity

The space complexity of this approach is **O(1), **because we are not using auxiliary space here**. **

Also see, __Rabin Karp Algorithm__