可能重复：   Fast算法可以迅速找到号码属于一个范围集合的范围？

鉴于这是不重叠的和排序（rangeList）号码范围的列表，和一个号码，编写一个有效的算法首先找到（部分范围中）rangeList是否存在此数目，如果它存在，返回正确的范围内。

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.

例如rangeList = [（ - 1，200），（300，2000），（2011，2300）]

For example rangeList = [(-1, 200), (300, 2000), (2011, 2300)]

查询1：1000 - >（真，（300，2000））自1000位于300和2000之间。

Query 1: 1000 -> (True, (300, 2000) ) since 1000 lies between 300 and 2000.

问题2：250 - >（假，（无，无）），因为没有250不在列表中的任何范围存在

Query 2: 250 -> (False, (None, None) ) since no 250 does not exist in any range in the list.

最好的算法，我想出了是使用二进制搜索日志N。这感觉就像尤其是对经度/纬度基于搜索一个非常普遍的问题。任何想法，使这个比数N +

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?

推荐答案

我不知道这将完成你想要的，但它是一个镜头。这将包括为O（n）preprocessing一步，作为回报，将提供一个机会，在O（1）运行时间对于任何给定的查询对空间复杂度平衡（通过参数C）。如果您rangeList经常变化，这可能不会是有帮助的。

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步骤：

Preprocessing steps:

找到总范围范围之列（可接受的最低值和最高的，尽管会有差距之间）。 O（1）

Find the "total range" of the list of ranges (lowest acceptable value and highest, though there will be gaps in between). O(1)

选择一个浓度参数C（整数）为你想有多少个在这个范围内进行评估。 O（1）

Select a concentration parameter c (integer) for how many points you'd like to evaluate in that range. O(1)

创建一个映射功能，整数[1，C]映射到步骤1中找到的总范围，也可以做相反的（这是没有更复杂的超过摄氏，华氏转换）。也为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)

使用映射函数，确定对应于[1，C]在总的范围之分。通过扫描范围的列表中，当您去评估这些点，存放在长度C数组的答案（（真，（300，2000））等）（我们称之为数组评为）。 O（N + C）

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)

在收到的查询：

使用映射函数的查询号码转换，在总范围 - > [1，C]方向。如果转换后的数字超出范围[1，C]，返回（假，无，无）。 O（1）

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)

取转换数字的天花板和地板，它会给你两个整数a和b。比较评估的[a]和评估的并[b]。如果它们包含了相同的答案，返回它（如果你的转换后的数字已经是一个整数，返回评估的[转换后的数字]直接）。 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)

如果求值[A]和评估[B]给出不同的答案，你必须做一个二进制搜索。但你至少可以启动A和B之间的搜索在半路，映射回范总。

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".