CODEWITHSUNDEEP
c++vectorbinary-search
someone12321
someone12321

Reputation: 755

How to make lower bound binary search if we have vector of pairs

I'm trying to implement lower_bound function in my c++ program, but the problem is next: it works fine with vector but it fails if we have to search over vector of pairs

I have one vector of pairs and i want to search first the first member of the pair and if we have multiple values with same value i want to return the smallest of the second value, for example:

Let's say we have the following vector of pairs

v = {(1,1),(2,1),(2,2),(2,3),(3,4),(5,6)};

Let's say we are searching for value K = 2, now I want to return the position 1 (if the array is 0-indexed) because the second value of the pair is 1 and 1 is smallest.

How can I implement this in easiest way, I tried implementing this but it fails in compiling, here is my code:

vector<pair<int,int> >a,b;
void solve() {
sort(b.begin(), b.end());
sort(a.begin(), a.end());

vector<int>::iterator it;
for(int i=0;i<a.size();i++) {
    ll zero=0;
    int to_search=max(zero, k-a[i].first);

    it=lower_bound(b.begin(), b.end(), to_search);
    int position=it-b.begin();

    if(position==b.size()) continue;
    answer=min(answer, a[i].second+b[position].second);
}
}

In other words I'm searching for the first value, but if there are more of that value return the one with smallest second element.

Thanks in advance.

Upvotes: 0

Views: 598

Answers (1)

Jarod42
Jarod42

Reputation: 217810

less operator work on pair, so you may use directly

std::lower_bound(v.begin(), v.end(), std::make_pair(2, std::numeric_limits<int>::min()));

Upvotes: 2

Related Questions