可能重复：
Fast Algorithm to Quickly Find the Range a Number Belongs to in a Set of Ranges?动态范围搜索
鉴于这是不重叠的和排序（rangeList），和多个号码的范围的列表，写一个有效的算法先找到这个数字是否存在于rangeList中的某个范围内，如果它存在，返回正确的范围。
例如rangeList = [（ - 1，200），（300，2000），（2011，2300）]
查询1：1000 - >（True时，（300，2000）），因为1000的谎言在300和2000之间。
查询2：250 - >（False，（None，None）），因为列表中的任何范围都不存在250。
我提出的最好的算法是log N使用二进制搜索。这感觉是一个非常常见的问题，特别是对于基于经度/纬度的搜索。任何想法都比log N更好？
我不确定这会完成你想要的，但它是一个镜头。这将涉及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）
在接收到查询：
使用映射函数来查询号码转换成 “总范围” - > [1，C]方向。如果转换的数字超出范围[1，c]，则返回（False，None，None）。 O（1）
取出转换后数字的上限和下限，这会给出两个整数a和b。比较评估[a]和评估[b]。如果它们包含相同的答案，则返回它（如果您的转换号码已经是整数，则直接返回Evaluated [转换后的号码]）。 O（1）
如果评估[a]和评估[b]给出不同的答案，则必须进行二分搜索。但你至少可以在a和b之间的中途开始搜索，并将其映射回“总范围”。
伟大的问题。我想不出任何更好的，不涉及硬编码散列函数。 – Cephron
谢谢。你能否详细说明硬编码哈希？你的意思是记忆吗？ – GeneralBecos
类别。我会发布一个答案... – Cephron