如何构建区间到数值的常数时间查找映射？是否存在可行方案？

字典存区间作为键的方案可行性 #

这个方案无法实现常数时间查找，原因如下：

• 字典的键值匹配是严格的哈希等值匹配，你输入的查询值是单个整数n，无法直接和作为键的区间对象做等值匹配，必须遍历所有字典的键逐一判断n是否落在当前区间内，时间复杂度是O(k)，k为区间总数量，不属于常数时间。
• 额外兼容问题：大多数编程语言中，列表/区间这类可变对象无法作为字典的哈希键，需要额外转成元组等不可变类型才能存入，就算存入也解决不了上述的匹配逻辑问题。

可行的实现方案 #

方案1：数组下标直接映射（严格O(1)查询，适合n取值范围小的场景） #

如果n的可能取值范围上限可控（比如最大值不超过1e5），可以直接初始化一个长度覆盖所有可能n的数组，每个下标位置存储对应区间的映射值：

• 示例中你可以初始化数组长度为67（覆盖1_{66），下标1}3赋值-2，4~10赋值-3，以此类推
• 查询时直接取arr[n]即可，完全满足常数时间要求
• 缺点：如果n的取值范围极大（比如上限到1e9），会占用大量冗余内存，不适用。

方案2：有序区间二分查找（近似常数时间，适合n范围大、区间数量少的场景） #

因为绝大多数区间映射场景的区间都是无重叠、有序、无间隙的（你给出的示例也符合这个特征），可以提前提取所有区间的左端点排序，和对应的映射值组成两个有序列表：

• 示例中左端点列表为[1,4,11,26,45]，对应映射值列表为[-2,-3,-4,-5,-6]
• 查询时用二分查找找到最后一个小于等于n的左端点的索引，直接取对应位置的映射值即可，时间复杂度为O(logk)，k为区间数量，当k小于1e4时logk不到14，性能和常数时间几乎无差异
• 优点：内存占用极低，哪怕n上限到1e9也不受影响，实现简单不易出错。

方案3：全量值哈希映射（严格O(1)，适合区间覆盖范围小的场景） #

如果区间覆盖的整数总量不大，你可以直接把区间内的所有整数都作为键存入字典，对应值为映射值：

• 示例中你可以把1、2、3都作为键存值-2，4到10作为键存值-3，以此类推
• 查询时直接dict.get(n)就可以得到结果，是严格的常数时间
• 缺点：如果区间覆盖的整数总量很大，初始化字典的时间和内存成本都很高，适用场景有限。

内容的提问来源于stack exchange，提问作者Patrick_Chong