1.
Introduction
1.1.
Problem Statement
1.2.
Vector of pairs
1.3.
Sample Example
1.4.
Algorithm
1.5.
Implementation
2.
Search for a key in a sorted vector of pairs
2.1.
Pseudocode
2.2.
Implementation
2.2.1.
Time complexity
2.2.2.
Space complexity
3.
3.1.
What is binary search?
3.2.
What are vectors?
3.3.
What is the C++ STL library?
3.4.
What is the time complexity of Binary search in the sorted vector of pairs?
4.
Conclusion
Last Updated: Mar 27, 2024
Easy

# Binary Search in Sorted Vector of Pairs

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

1. Initializing vector of pairs.
2. Insert value in vectors.
3. Displaying the values of vectors.
4. 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

### What is binary search?

The binary search is a searching algorithm that divides the search interval in half repeatedly in a sorted array. The idea behind binary search is to use the array's sorted information to reduce the time complexity to O(log n).

### What are vectors?

Vectors are similar to dynamic arrays in that they can resize themselves automatically when an element is added or removed.

### What is the C++ STL library?

C++ STL (standard template library) is a C++ language software library that contains templates for containers, iterators, algorithms, and function objects.

### What is the time complexity of Binary search in the sorted vector of pairs?

The time complexity of Binary search in a sorted vector of pairs is O(n*log n), we are using the algorithm of binary search, i.e. by finding the middle element and comparing it with other adjacent elements and then so on. The concept of divide and conquer is being used.

## Conclusion

This article extensively discussed the binary search in the sorted vector of pairs. We hope this blog has helped you enhance your knowledge regarding the array of searching problems. After reading about the binary search in sorted vector of pairs, are you not feeling excited to read/explore more articles on this topic? Don't worry; Coding Ninjas has you covered. Check out our articles Level Order Traversal Of  A Binary TreePrint the node values at odd levels of a Binary treeReplace each node in a binary tree with the sum of its inorder predecessor and successor, and many more on our Website.

Recommended problems -

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio!

But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Live masterclass