针对一群范围对的最快查找算法设计(不要用数组)

描述如下:

假如有一群范围对,格式为:<范围表示,该范围对应的结果值>,设计一个最快查找算法,使得给定一个值,输出该值所在范围对的结果值。
注意1:范围对之间没有交集,即不可能存在<1, 10>和<2, 11>这样的两个范围对。

注意2:各个区间不一定严格相邻,也就是可能只有<1, 3>和<99, 201>这样两个区间,所以STL中的lower_bound不适用。

例如有以下几个范围对:
<<1, 2>, 20>
<<3, 37>, 27>
<<48, 57>, 28>
<<58, 63>, 27>
<<97, 128>, 122>
<<129, 149>, 12>
<<150, 189>, 13>
<<200, 245>, 14>
<<246, 256>, 129>
<<479, 560>, 12>

假如给定一个数100,则根据题意应输出122,因为100属于范围对<97, 128>

要求:不要用范围对作为下标用数组来存储,因为范围对可能非常大。

这里是我自己的解法:http://www.cnblogs.com/lanxuezaipiao/p/3802699.html
这里是知乎用户的解答:http://www.zhihu.com/question/24236515

大家还有更好的idea吗?

评论 (0)链接2014-06-23 
德问是一个专业的编程问答社区,请 登录注册 后再提交答案