Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
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.
Frequently Asked Questions
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

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

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!

Previous article
Ceiling in a sorted array
Next article
Find the only repetitive element between 1 to n-1
Live masterclass