如何在C++中用二分查找搜索pair？请修改代码实现精确匹配

Hey there! The issue with your original code is that your custom compare struct is set up to compare pairs with integers, which only checks the first element of the pair. To find an exact pair, we need to compare pairs directly—luckily, C++'s std::pair already has a built-in comparison operator that does exactly what we need (compares first elements, then second elements if the first are equal).

Here's the modified code that correctly searches for an exact pair:

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

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 using default pair ordering (first element, then second)
    sort(vect.begin(), vect.end());
    
    // Print sorted vector
    cout << "KEY" << '\t' << "ELEMENT" << endl;
    for (auto& x : vect)
        cout << x.first << '\t' << x.second << endl;
    
    // Define the exact pair we want to search for
    pair<int, int> target = make_pair(3, 29);
    cout << "\nSearching for pair (" << target.first << ", " << target.second << ") in vector" << endl;
    
    // Binary search for the exact pair (uses default pair comparison)
    if (binary_search(vect.begin(), vect.end(), target))
        cout << "Exact pair found!";
    else
        cout << "Exact pair not found.";
    
    return 0;
}

Key Changes Explained: #

• Removed the custom compare struct: We don't need it anymore because we're now comparing pairs directly, and the default std::pair comparison matches the sorted order of our vector.
• Changed the search target to a pair: Instead of searching for an integer like 3, we define an exact pair (e.g., (3, 29)) that we want to find.
• Used default binary_search: Since we sorted the vector with the default sort function (which uses the built-in pair ordering), the default binary_search will correctly check for the exact pair by first comparing the first elements, then the second elements if needed.

Optional: Custom Comparator (If You Need It) #

If you ever need to use a custom ordering (e.g., sort by second element first), you can define a comparator struct for pairs and use it in both sort and binary_search:

struct CustomPairComparator {
    bool operator()(const pair<int, int>& a, const pair<int, int>& b) {
        // Sort by second element first, then first
        if (a.second != b.second) {
            return a.second < b.second;
        }
        return a.first < b.first;
    }
};

// Then in main:
sort(vect.begin(), vect.end(), CustomPairComparator());
if (binary_search(vect.begin(), vect.end(), target, CustomPairComparator())) {
    // ...
}

Just remember: always use the same comparator for both sorting and binary search—otherwise, the search won't work correctly!

内容的提问来源于stack exchange，提问作者Kriso