algorithm - 如何在巨大的范围值对中快速搜索？

Question

例如我们有一些范围值对:

<<1, 2>, 65>
<<3, 37>, 75>
<<45, 159>, 12>
<<160, 200>, 23>
<<210, 255>, 121>

而且这些范围是不相交的。

给一个整数78 ，对应的范围是<45, 159> , 所以输出值 12 .

由于范围可能非常大，我现在使用 map存储这些范围值对。每次搜索都会扫描整个 map 集，它是 O(n) .

除了二分查找还有什么好的方法吗？

Answer 1

二分查找绝对是您的最佳选择。 O(log n) 很难被击败!

如果您不想手动编写二进制搜索代码，并且您使用的是 C++，则可以使用 std::map::upper_bound 函数，它实现了二进制搜索:

std::map<std::pair<int, int>, int> my_map;
int val = 78; // value to search for
auto it = my_map.upper_bound(std::make_pair(val, val));
if(it != my_map.begin()) it--;
if(it->first.first <= val && it->first.second >= val) {
    /* Found it, value is it->second */
} else {
    /* Didn't find it */
}

std::map::upper_bound 保证以对数时间运行，因为 map 本质上是排序的(通常实现为红黑树)。它返回您正在搜索的元素之后的元素，因此它返回的迭代器会递减以获得有用的迭代器。