动态范围搜索
可能的重复：
快速算法快速找到一组范围中某个数字所属的范围？
给定一个不重叠且已排序的数字范围列表（rangeList）和一个数字，编写一个有效的算法，首先查找该数字是否存在于 rangeList（某个范围）中，如果存在，则返回正确的范围。
例如 rangeList = [(-1, 200), (300, 2000), (2011, 2300)]
查询 1: 1000 -> (True, (300, 2000) )，因为 1000 位于 300 和 2000 之间。
查询 2：250 -> (False, (None, None) ) 因为 no 250 不存在于列表中的任何范围内。
我想出的最好的算法是使用二分搜索的 log N。这感觉像是一个非常常见的问题，特别是对于基于经度/纬度的搜索。有什么想法可以让它比 log N 更好吗？
Possible Duplicate:
Fast Algorithm to Quickly Find the Range a Number Belongs to in a Set of Ranges?
Given a list of range of numbers that are non-overlapping and sorted (rangeList), and a number, write an efficient algorithm to find first whether this number exists in (some range in) rangeList and if it does exist, return the correct range.
For example rangeList = [(-1, 200), (300, 2000), (2011, 2300)]
Query 1: 1000 -> (True, (300, 2000) ) since 1000 lies between 300 and 2000.
Query 2: 250 -> (False, (None, None) ) since no 250 does not exist in any range in the list.
The best algorithm I have come up with is log N using binary search. This feels like a very common problem especially for Longitude/Latitude based searches. Any ideas to make this better than log N?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我不确定这是否会实现你想要的，但这是一个尝试。它将涉及 O(n) 预处理步骤，并且作为回报，将为任何给定查询提供 O(1) 运行时间（通过参数 c）平衡空间复杂度的机会。如果您的 rangeList 经常更改，这可能没有帮助。
预处理步骤：
查找范围列表的“总范围”（可接受的最低值和最高值，尽管之间会有间隙）。 O(1)
选择一个浓度参数 c（整数）来表示您想要在该范围内评估的点数。 O(1)
创建一个映射函数，将整数 [1, c] 映射到步骤 1 中找到的总范围，并且还可以执行逆操作（这并不比摄氏度 - 华氏度转换更复杂）。还可以 O(1)
利用映射函数，确定总范围内与[1, c]对应的点。扫描范围列表，随时评估这些点，将答案（(True, (300, 2000)) 等）存储在长度为 c 的数组中（我们将数组称为“Evaluated”）。 O(n + c)
收到查询后：
使用映射函数将查询数转换为“总范围”->O(n + c) [1，c]方向。如果转换后的数字超出范围 [1, c]，则返回 (False, None, None)。 O(1)
取转换后数字的上限和下限，这将得到两个整数 a 和 b。比较已评估的[a] 和已评估的[b]。如果它们包含相同的答案，则返回它（如果您转换后的数字已经是整数，则直接返回 Evaluated[converted number]）。 O(1)
如果 Evaluated[a] 和 Evaluated[b] 给出不同的答案，则必须进行二分查找。但您至少可以在 a 和 b 之间的中间开始搜索，映射回“总范围”。
I'm not sure this will accomplish what you want, but it's a shot. It would involve an O(n) preprocessing step, and in return would offer a chance at O(1) runtime for any given query balanced against space complexity (via the parameter c). If your rangeList changes frequently, this will probably not be helpful.
Preprocessing steps:
Find the "total range" of the list of ranges (lowest acceptable value and highest, though there will be gaps in between). O(1)
Select a concentration parameter c (integer) for how many points you'd like to evaluate in that range. O(1)
Create a mapping function that maps integers [1, c] to the total range found in step 1, and can also do the inverse (this is no more complicated than a Celsius-Farenheit conversion). also O(1)
Using the mapping function, determine the points in the total range that correspond to [1, c]. Scan through the list of ranges, evaluating these points as you go, storing the answers ( (True, (300, 2000)), etc.) in an array of length c (let's call the array "Evaluated"). O(n + c)
Upon receiving a query:
Use the mapping function to convert the query number in the "total range" -> [1, c] direction. If the converted number falls outside the range [1, c], return (False, None, None). O(1)
Take the ceiling and floor of the converted number, which will give you two integers a and b. Compare Evaluated[a] and Evaluated[b]. If they contain the same answer, return it (if your converted number was already an integer, return Evaluated[converted number] directly). O(1)
If Evaluated[a] and Evaluated[b] give different answers, you have to do a binary search. But you can at least start the search at halfway between a and b, mapped back into "total range".