如何在已有SortedList中结合键函数使用二分查找？

SortedList自带的bisect_right确实只支持按元素本身比较，但可以通过以下几种方式实现类似bisect模块结合键函数的二分查找：

方法一：存储键值与原始元素的元组 #

这是最直观且稳定的方案，把元素包装成(键值, 原始元素)的元组存入SortedList，利用元组的自然排序特性（先比较第一个元素，即键值），直接用目标键值构造一个“上限元组”来调用bisect_right。

示例代码：

from sortedcontainers import SortedList

# 按字符串长度排序，存储(长度, 字符串)元组
sorted_list = SortedList()
sorted_list.add((3, "abc"))
sorted_list.add((5, "hello"))
sorted_list.add((5, "world"))
sorted_list.add((7, "python"))

# 模拟bisect_right：找键值<=5的元素的插入位置
target_key = 5
# 用float('inf')作为元组第二个元素，确保比所有原始元素都大
insert_pos = sorted_list.bisect_right((target_key, float('inf')))

# 获取所有键值<=5的原始元素
result = [item[1] for item in sorted_list[:insert_pos]]
print(result)  # 输出: ['abc', 'hello', 'world']

方法二：利用SortedList的key参数+自定义包装类 #

如果不想修改存储的元素结构，可以借助SortedList初始化时指定的key参数，配合一个自定义的包装类来实现基于键值的比较，再用bisect模块的bisect_right方法。

示例代码：

from sortedcontainers import SortedList
import bisect

# 初始化SortedList时指定排序键为字符串长度
sorted_list = SortedList(key=lambda x: len(x))
sorted_list.update(["abc", "hello", "world", "python"])

target_key = 5

# 自定义包装类，重载__lt__方法来比较键值
class KeyMatcher:
    def __init__(self, target):
        self.target = target
    def __lt__(self, element):
        # 用SortedList内部的_key方法获取元素的键值，和目标键比较
        return self.target < sorted_list._key(element)

# 调用bisect_right找到插入位置
insert_pos = bisect.bisect_right(sorted_list, KeyMatcher(target_key))
print(insert_pos)  # 输出: 3

注意：这种方法用到了SortedList的内部方法_key，虽然能工作，但属于非公开API，未来版本可能变动，谨慎使用。

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