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 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 !!
Leave a Reply