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

如果列表是按升序排序的，那么已经有一个主题介绍了如何在Python中使用对分模块进行二进制搜索：Binary search (bisection) in Python
有没有一个好的方法来对一个反向排序的列表进行二进制搜索？

最佳答案

这就是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

如果你需要的话，它的行为就像是在最后。下面是对反向数组的一个示例用法：

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

关于python - Python中反向排序列表的二进制搜索，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/29045162/