SexyBeast - 4 months ago 19

C++ Question

I have a vector of

`pairs`

`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`

Given a

`pair`

`pair`

`pair`

`<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`

`lower_bound`

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

Answer

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.