Python中如何实现按左闭右开区间匹配的有序键值查询结构？

需求说明 #

需要存储有序的区间下界与对应值的映射，示例映射规则如下：

原始字典写法为d = {1: "pear", 4: "banana", 7: "orange"}，要求输入任意数值时自动匹配所属区间，返回对应值。
已排查方案：intervalTrees功能过重且支持重叠区间，不符合需求；原生字典不支持区间匹配，无法直接满足要求。

可用实现方案 #

两种方案的匹配逻辑都基于二分查找，时间复杂度为O(log n)，性能足以应对绝大多数场景：

方案1：使用Python标准库bisect（无第三方依赖） #

不需要安装额外依赖，适合轻量使用场景：

import bisect

# 存储排序好的(下界, 值)元组
d = [(1, "pear"), (4, "banana"), (7,"orange") ]
# 提取单独的下界列表用于二分查找
keys = [j[0] for j in d]

# 测试用例：输入1-9验证匹配结果
for v in range(1,10):
    print("当前输入值：", v)
    # 二分查找得到第一个大于v的键的索引，减1即为对应区间的下界索引
    i = bisect.bisect(keys, v) - 1
    out = d[i]
    print("匹配结果：", out)
    print("")

方案2：使用SortedDict（适合频繁增删映射的场景） #

如果需要经常新增、删除区间映射，可以用第三方库sortedcontainers提供的SortedDict，它会自动维护键的有序性，无需手动同步下界列表：

from sortedcontainers import SortedDict

d2 = SortedDict()
d2[1] = 'pear'
d2[4] = 'banana'
d2[7] = 'orange'

# 测试用例：输入1-9验证匹配结果
for v in range(1,10):
    print("当前输入值：", v)
    i = bisect.bisect(d2.keys(), v) - 1
    j = d2.keys()[i]
    out = d2[j]
    print("匹配结果：", out)
    print("")

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