为什么python的'bisect'模块（二进制搜索）不允许将其与特定的'key'一起使用？

Question

来自文档的报价：

https://docs.python.org/3/library/bisect.html

与sorted（）函数不同，它对bisect（）没有意义函数具有关键或相反的参数，因为这将导致低效的设计（对等分函数的成功调用不会“记住”以前的所有键查询。

相反，最好搜索预先计算的密钥列表以找到相关记录的索引：

>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
>>> data.sort(key=lambda r: r[1])
>>> keys = [r[1] for r in data]         # precomputed list of keys
>>> data[bisect_left(keys, 0)]
('black', 0)

但是建议的解决方案适用于O(N)（创建键列表），而不适用于O(logN)（假设需要为一个列表一次调用bisect）。

是否有内置的二进制搜索，允许使用自定义键进行搜索？

（除了传递的对象的重载operator __lt__()。]

如果没有，那么为什么python没有呢？ （假设标语为“包括电池”）

Answer 1

bisect和insort的参数不一致，或者必须传递一个值而不是键来进行搜索。不管哪种方式，someone都会带来不幸的惊喜。

即，是

def insort(a, x, lo=0, hi=None, *, key=None):
    lo = bisect(a, x, lo, hi, key)
    a.insert(lo, x)

def bisect(a, x, lo=0, hi=None, *, key=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    if key is None:
        key = lambda x: x
    while lo < hi:
        mid = (lo+hi)//2
        if key(x) < key(a[mid]): hi = mid
        else: lo = mid+1
    return lo

>>> key=lambda r: r[1]
>>> insort(data, ('green', 3), key=key)
>>> bisect(data, 7, key=key) # error comparing tuple to int

或替代地

def insort(a, x, lo=0, hi=None, *, key=None):
    if key is None:
        key = lambda x: x
    lo = bisect(a, key(x), lo, hi, key)
    a.insert(lo, x)

def bisect(a, x, lo=0, hi=None, *, key=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    if key is None:
        key = lambda x: x
    while lo < hi:
        mid = (lo+hi)//2
        if x < key(a[mid]): hi = mid
        else: lo = mid+1
    return lo

>>> key=lambda r: r[1]
>>> item = ('green', 3)
>>> insort(data, item, key=key)
>>> bisect(data, item, key=key) # error comparing int to tuple