SexyBeast - 1 year ago 94
C++ Question

# 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();
``````

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, make_pair(prev(u_it)->first, 10),
[](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.