python - Python中反向排序列表的二进制搜索

Question

如果列表按升序排序，已经有一个关于如何使用 bisect 模块在 Python 中进行二进制搜索的主题:Binary search (bisection) in Python

有没有一种对倒序排列的列表进行二分查找的好方法？

Answer 1

这就是documentations说:

Unlike the sorted() function, it does not make sense for the bisect() functions to have key or reversed arguments because that would lead to an inefficient design (successive calls to bisect functions would not “remember” all of the previous key lookups).

所以不支持自定义顺序。任何绕过它的尝试(例如将列表反转两次，或准备一个单独的键列表)都将花费线性时间，这完全破坏了二分搜索的点，它是对数的。

这是一个接受比较器的二分查找的实现

def bisect(arr, val, cmp):
    l = -1
    r = len(arr)
    while r - l > 1:
        e = (l + r) >> 1
        if cmp(arr[e], val): l = e
        else: r = e
    return r

它的行为类似于bisect_right，如果您需要bisect_left，请在最后返回l。以下是反向数组的示例用法:

>>> a = [10**8 - x for x in range(10**8)]
>>> bisect(a, 100, lambda x, y: x > y)
99999900