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

Question

[已经有一个话题，如果使用bisect模块将列表以升序排序，如何在Python中进行二进制搜索：Binary search (bisection) in Python

是否有一种很好的方法可以对按反向排序的列表进行二进制搜索？

Answer 1

这是documentations所说的：

与sorted（）函数不同，bisect（）函数具有键或相反的参数是没有意义的，因为那样会导致效率低下的设计（对bisect函数的成功调用不会“记住”所有先前的键查找）。

因此，它不支持自定义顺序。任何绕过它的尝试（例如两次反转列表或准备单独的键列表）都将花费线性时间，这完全破坏了二进制搜索的对数点。

这里是接受比较器的二进制搜索的实现

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，则其行为类似于return l，bisect_left。这是反向数组的示例用法：

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

Answer 2

在这种情况下，具有代码片段来复制库函数是有益的，例如下面的bisect_left和bisect_right。通过将<（或<=）更改为>（或>=），可以对等式搜索降序数组。