如何快速搜索巨大的范围-值对

Question

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

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

这些范围是不相交的

给定一个整数78，对应的范围是<45, 159>，因此输出值12。

由于范围可能非常大，我现在使用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本身是排序的(并且通常实现为红黑树)。它返回所查找的元素后面的元素，因此它返回的迭代器是自减的，以获得一个有用的迭代器。

Answer 2

二叉搜索树呢?

虽然你可能需要一个自平衡搜索树:AVL树和红黑树是一个很好的开始，但你可能应该坚持在你的。net"生态系统"中已经有了一些东西，那将是一个SortedDictionary，可能有一个costum comparer，但这只是一个例子…

---

对于c++，你应该使用有序映射，在这里使用自定义比较

链接:http://en.wikipedia.org/wiki/Binary_search_treehttp://en.wikipedia.org/wiki/AVL_treehttp://en.wikipedia.org/wiki/Red-black_treehttp://msdn.microsoft.com/en-us/library/f7fta44c%28v=vs.110%29.aspxhttp://msdn.microsoft.com/en-us/library/8ehhxeaf (v = vs.110) . aspxhttp://www.cplusplus.com/reference/map/map/

---

对于c++，我会这样做(没有编译器，所以小心):

class Comparer 
{
    bool operator()(pair<int,int> const & one, pair<int,int> const & two) 
    {
        if (a.second < b.first) 
        {
            return true;
        }
        else
        {
        return false;
        }
     }
};

则将映射定义为:

map<pair<int,int>,int,Comparer> myMap;
myMap.insert(make_pair(make_pair(-3,9),1));
int num = myMap[make_pair(7,7)]