mardi 4 avril 2017

How to use algorithm.h's binary search on a vector of pairs if the vector is sorted on the basis of first value.

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
bool comp(const pair<int,int> &a,const pair<int,int> &b)
{
    return (a.first < b.first);
}

int main(void)
{
    vector<pair<int,int>> data;
    data.push_back(make_pair(1,7));
    data.push_back(make_pair(5,5));
    data.push_back(make_pair(2,7));
    data.push_back(make_pair(6,7));
    data.push_back(make_pair(9,6));
    data.push_back(make_pair(2,4));
    data.push_back(make_pair(2,8));
    sort(data.begin(),data.end());
    int key=9;
    if(binary_search(data.begin(),data.end(),key,comp))
    {
        cout<<"Key found"<<endl;
    }
    else
    {
        cout<<"Key is not found"<<endl;
    }
}

  1. Here the vector data is sorted on the basis of the first value and i need to apply binary search on the first values of every pair.
  2. I am aware that key must be of type pair but i am confused by the behavior as why do i need to supply a dummy second value eg. pair key=make_pair(9,9) ? So please explain the behavior too.

Aucun commentaire:

Enregistrer un commentaire