Using binary_search on a vector of pairs when the vector is sorted by its first value

Question

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

Answer 1

You could define the comparison within a struct for (pair, int) and (int, pair), so the comparisons within binary search know how to compare a pair with an int:

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

struct comp_pair_int {
    bool operator()(const pair<int,int> &a, const int & b)
    {
        return (a.first < b);
    }
    bool operator()(const int & a,const pair<int,int> &b)
    {
        return (a < 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_pair_int()))
    {
        cout<<"Key found"<<endl;
    }
    else
    {
        cout<<"Key is not found"<<endl;
    }
}