CODEWITHSUNDEEP
c++11stl-algorithm
Crosk Cool
Crosk Cool

Reputation: 734

Using binary_search on a vector of pairs when the vector is sorted by its 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.

Upvotes: 0

Views: 4913

Answers (2)

MSalters
MSalters

Reputation: 179887

It's mostly a matter of names. binary_search searches for elements, so you need to provide an element.

There's also std::partition_point(begin,end, predicate), which assumes a partitioned range. A range is partitioned if there's one point in the range such that all elements before it satisfy the predicate and the elements after it do not. (either sub-range can be empty),

Now, any sorted range is also partitioned if you bind the sorting predicate with any value. E.g. the range 1,5,8 is partioned by value<3 but also by value<0 or value<100. In your case, you can define a lambda predicate [key](std::pair<int,int> p){ return p.first<key; }.

Upvotes: 1

W.Mann
W.Mann

Reputation: 923

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;
    }
}

Upvotes: 2

Related Questions