STL 排序向量查找小于或等于给定值的第一个元素

Question

我有一个向量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} };

pairs 按第一个元素排序。

给定一个 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>)

条件：我只需要使用 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 1

std::lower_bound returns 第一个项大于或等于给定值

你需要

+1 到 std::lower_bound
-1 到 std::lower_bound

求值（或者你可以使用std::upper_bound）

并再次使用 std::lower_bound 找到正确的配对

例子

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

顺便说一句，您不需要向 lower_bound

提供 pair

如果你只使用lower_bound，你只需要一个比较器

Answer 2

既然你想要第一对，你可能想要合并下限和上限？

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

}

输出：

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

PS - 在 WhozCraig 发表评论后更新了答案：

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).

现在的答案满足所有您提供的测试用例（我在这里不显示）。希望有帮助！ :)

附录：

参考 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。

STL 排序向量查找小于或等于给定值的第一个元素

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

c++

algorithm

stl

vector

binary-search