c++ - 通过包含两个变量的键进行二进制搜索

Question

我有一个已排序的对 (x,y) 数组，它们按 x 排序，对于相同的 x，它们按 y 排序。为了澄清，一个例子是 (2,3),(2,4),(3 ,2),(3,4),(3,5)。对于给定的对 (a,b)，我想找到对 (c,d) 使得 c>a 和 d>b 使得 c 和 d 最小。我觉得这可以通过二进制搜索来完成，但我不知道如何。与此相关的任何帮助或链接。

Answer 1

因为您有条件 c>a 和 d>b，我们将首先搜索可接受的 c 值，然后搜索最小的 d 。

auto compare_first = [](std::pair<int, int> const & a, std::pair<int, int> const & b){
    return a.first < b.first;
};

auto compare_second = [](std::pair<int, int> const & a, std::pair<int, int> const & b){
    return a.second < b.second;
};

std::vector<std::pair<int, int>> values { {2,3}, {2,4}, {3,2}, {3,4}, {3,5} };

std::pair<int, int> value { 2, 3 };

auto it_c = std::upper_bound(values.begin(), values.end(), value, compare_first);
auto it = std::upper_bound(it_c, values.end(), value, compare_second);

Live on ideone