CODEWITHSUNDEEP
c++algorithmvectorstlbinary-search
NedStarkOfWinterfell
NedStarkOfWinterfell

Reputation: 5153

STL sorted vector find first element less than or equal to given value

I have a vector of pairs. Suppose it is like this:

vector<pair<int,int>> vec = { {1,12}, {1,5}, {1,6}, {1,9}, {3,9}, {3,11}, {3,13}, {3,4}, {5,9}, {5,91}, {13,8}, {16,8}, {20,8}, {20,81} };

The pairs are sorted by first element.

Given a pair, I need to find the index of the last pair in the vector whose first element is less than or equal to first element of the given pair. If for that last pair, other pairs lie to its left with the same value of the first element, I need the first of all those pairs:

<4,10> => 4 (vec[4] is <3,9>, the elements with the largest first value less than or equal to 4 are those with first element as 3, and there are 4 pairs with a 3 in the first element, at indices 4-7, so return the first of those pairs)

<0,10> => -1, since no element exists to its right.

<1,6> => 0 (vec[0] is <1,12>. There is no pair whose first element is less than 1, and there are 4 pairs, including <1,6> whose first element is 1. So we need the first of these 4 pairs.)

<23,81> => 12 (vec[12] is <20,8>)

Condition: I need to use only standard algorithms like upper_bound, binary_search and lower_bound. I tried this, but it is failing badly:

vector<pair<int,int>> vec = { {1,12}, {1,5}, {1,6},{1,9}, {3,9}, {3,11}, {3,13}, {3,4}, {5,9}, {5,91}, {13,8}, {16,8}, {20,8}, {20,81} };

auto i = std::lower_bound(vec.begin(), vec.end(), make_pair<int,int>(4,10),
    [](const pair<int,int>& f1, const pair<int,int>& f2) { return f1.first < f2.first; });

cout << i-vec.begin();

Upvotes: 4

Views: 4768

Answers (2)

apple apple
apple apple

Reputation: 10591

std::lower_bound returns the first item greater or equal to the given value

you need to

  • +1 to the input of std::lower_bound
  • -1 to the result of std::lower_bound

to find the value (or you can use std::upper_bound)

and use std::lower_bound again to find the right pair

example

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

int my_find(const vector<pair<int,int>>& vec, int value){
   auto comparer = [](const pair<int,int>& f1, int value) { return f1.first < value; };

   auto i = std::lower_bound(vec.begin(), vec.end(), value+1, comparer);
   if(i==vec.begin()){return -1;}

   i = std::lower_bound(vec.begin(), vec.end(), (i-1)->first, comparer);
   return i-vec.begin();
}

int main(){

   vector<pair<int,int>> vec = { {1,12}, {1,5}, {1,6},{1,9}, {3,9}, {3,11}, {3,13}, {3,4}, {5,9}, {5,91}, {13,8}, {16,8}, {20,8}, {20,81} };

   cout << my_find(vec,-1) << '\n';
   cout << my_find(vec,3) << '\n';
   cout << my_find(vec,10) << '\n';
   cout << my_find(vec,100) << '\n';
}

BTW, you don't need to provide pair to lower_bound

and if you only use lower_bound, you need only one comparer

Upvotes: 1

gsamaras
gsamaras

Reputation: 73366

Since you want the first pair, you maybe want to combine lower and upper bound?

#include <algorithm>
#include <vector>
#include <utility>
#include <iostream>

using namespace std;

int main()
{
    vector<pair <int,int> > vec = { {1,12}, {1,5}, {1,6}, {1,9}, {3,9}, {3,11}, {3,13}, {3,4}, {5,9}, {5,91}, {13,8}, {16,8}, {20,8}, {20,81} };

    auto u_it = std::upper_bound(vec.begin(), vec.end(), make_pair<int,int>(4, 10),
        [](const pair<int,int>& f1, const pair<int,int>& f2) { return f1.first < f2.first; });

    if(u_it == vec.begin())
        cout << "-1\n";

    auto l_it = std::lower_bound(vec.begin(), u_it, *prev(u_it),
        [](const pair<int,int>& f1, const pair<int,int>& f2) { return f1.first < f2.first; });

    cout << l_it - vec.begin() << "\n";
    return 0;

}

Output:

Georgioss-MacBook-Pro:~ gsamaras$ g++ -Wall -std=c++0x main.cpp 
Georgioss-MacBook-Pro:~ gsamaras$ ./a.out 
4

PS - answer updated after WhozCraig's comment:

you want to use it = std::upper_bound(beg,end) to find the first strictly-greater element, and if that answers non-begin, then use std::lower_bound(beg,it) to find the lowest-matching ordinal of the element whose value is pulled from (it-1).

The answer now satisfies all the test cases you have provided (I am not showing it here). Hope that helps! :)

Appendix:

Ref for std::lower_bound, std::upper_bound and std::prev. Please notice how the std::lower_bound call uses std::make_pair without an initializing list, so that it lets the compiler come into play and resolve deduce the type.

Upvotes: 7

Related Questions