如何在C ++中应用二进制搜索来搜索点/对？

Question

我想使用二进制搜索来搜索配对向量中是否存在该配对。这是我的代码：此代码仅在查找配对中的第一个值：

您能否修改此代码以寻找确切的密码对？

#include <bits/stdc++.h> 
using namespace std; 

struct compare { 
    bool operator()(const pair<int, int>& value,  
                                const int& key) 
    { 
        return (value.first < key); 
    } 
    bool operator()(const int& key,  
                    const pair<int, int>& value) 
    { 
        return (key < value.first); 
    } 
}; 

int main() 
{ 
    vector<pair<int, int> > vect; 
    vect.push_back(make_pair(1, 20)); 
    vect.push_back(make_pair(3, 42)); 
    vect.push_back(make_pair(4, 36)); 
    vect.push_back(make_pair(2, 80)); 
    vect.push_back(make_pair(7, 50)); 
    vect.push_back(make_pair(9, 20)); 
    vect.push_back(make_pair(3, 29)); 

    sort(vect.begin(), vect.end()); 

    // printing the sorted vector 
    cout << "KEY" << '\t' << "ELEMENT" << endl; 
    for (pair<int, int>& x : vect) 
        cout << x.first << '\t' << x.second << endl; 

    // searching for the key element 3 
    cout << "search for key 3 in vector" << endl; 
    if (binary_search(vect.begin(), vect.end(), 
                                  3, compare())) 
        cout << "Element found"; 
    else
        cout << "Element not found"; 

    return 0; 
} 

Answer 1

如果要查找精确的配对，则需要将配对提供给binary_search，像这样

if (binary_search(vect.begin(), vect.end(), pair{3, 42}))
 // ... found

注意，这里不需要自定义compare函数。默认比较器做正确的事。 （实际上，您应该首先使用与sort元素相同的比较器，否则binary_search将被破坏）。