当向量按其第一个值排序时，对向量对使用 binary_search

Question

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
bool comp(const pair<int,int> &a,const pair<int,int> &b)
{
    return (a.first < b.first);
}

int main(void)
{
    vector<pair<int,int>> data;
    data.push_back(make_pair(1,7));
    data.push_back(make_pair(5,5));
    data.push_back(make_pair(2,7));
    data.push_back(make_pair(6,7));
    data.push_back(make_pair(9,6));
    data.push_back(make_pair(2,4));
    data.push_back(make_pair(2,8));
    sort(data.begin(),data.end());
    int key=9;
    if(binary_search(data.begin(),data.end(),key,comp))
    {
        cout<<"Key found"<<endl;
    }
    else
    {
        cout<<"Key is not found"<<endl;
    }
}

此处矢量数据是根据第一个值排序的，我需要对每对的第一个值应用二进制搜索。
我知道键必须是对类型，但我对这种行为感到困惑，因为为什么我需要提供一个虚拟的第二个值，例如。对键=make_pair(9,9) ?所以也请解释一下这种行为。

Answer 1

您可以在 (pair, int) 和 (int, pair) 的结构中定义比较，因此二进制搜索中的比较知道如何比较一个对与一个 int:

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

struct comp_pair_int {
    bool operator()(const pair<int,int> &a, const int & b)
    {
        return (a.first < b);
    }
    bool operator()(const int & a,const pair<int,int> &b)
    {
        return (a < b.first);
    }
};

int main(void)
{
    vector<pair<int,int>> data;
    data.push_back(make_pair(1,7));
    data.push_back(make_pair(5,5));
    data.push_back(make_pair(2,7));
    data.push_back(make_pair(6,7));
    data.push_back(make_pair(9,6));
    data.push_back(make_pair(2,4));
    data.push_back(make_pair(2,8));
    sort(data.begin(),data.end());
    int key=9;
    if(binary_search(data.begin(),data.end(), key,comp_pair_int()))
    {
        cout<<"Key found"<<endl;
    }
    else
    {
        cout<<"Key is not found"<<endl;
    }
}

Answer 2

主要是名字的问题。 binary_search 搜索元素，所以你需要提供一个元素。

还有 std::partition_point(begin,end, predicate)，它假定一个分区范围。如果范围中有一个点使得它之前的所有元素都满足谓词而其之后的元素不满足谓词，则该范围被分区。 (子区间可以为空),

现在，如果您将排序谓词与任何值绑定，任何排序的范围也会被分区。例如。范围 1,5,8 由 value<3 划分，但也由 value<0 或 value<100 划分。在您的情况下，您可以定义一个 lambda 谓词 [key](std::pair<int,int> p){ return p.first<key; }。

当向量按其第一个值排序时，对向量对使用 binary_search

Using binary_search on a vector of pairs when the vector is sorted by its first value

c++11

stl-algorithm