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