如何在Python的SortedDict中高效使用bisect/upper_bound方法？

DevOps 小满

2026-8-22

使用SortedDict实现O(logN)复杂度的键≤给定键的查找方案

SortedDict本身维护了有序的键集合，无需将键转为列表（该操作是O(N)复杂度），可直接利用其内置方法实现O(logN)的高效查找，以下是两种可行方案：

方案1：利用`bisect_right`方法

bisect_right会返回目标键插入到有序键序列中的位置（保持有序），该操作时间复杂度为O(logN)。通过这个位置，可直接定位到最大的≤目标键的元素：

from sortedcontainers import SortedDict

# 初始化有序字典
sorted_dict = SortedDict({2: "b", 4: "d", 6: "f", 8: "h"})
target = 7

# 获取插入位置
insert_pos = sorted_dict.bisect_right(target)

if insert_pos > 0:
    # 取前一个位置的键，即为最大的≤target的键
    max_key = sorted_dict.keys()[insert_pos - 1]
    print(f"符合条件的值：{sorted_dict[max_key]}")  # 输出f（对应键6）
else:
    print("不存在≤目标键的元素")

说明

如果目标键存在于字典中，bisect_right会返回该键的下一个位置，此时insert_pos - 1就是目标键本身，满足要求；
如果目标键不存在，insert_pos - 1指向的是最大的小于目标键的键。

方案2：利用`irange`方法

irange支持按范围查询键，配合reverse=True可直接从符合条件的最大键开始遍历，同样是O(logN)复杂度：

from sortedcontainers import SortedDict

sorted_dict = SortedDict({1: "a", 3: "c", 5: "e", 7: "g"})
target = 5

# 生成≤target的键的反向迭代器（从大到小）
valid_keys = sorted_dict.irange(maximum=target, reverse=True)

try:
    max_key = next(valid_keys)
    print(f"符合条件的值：{sorted_dict[max_key]}")  # 输出e（对应键5）
except StopIteration:
    print("不存在≤目标键的元素")