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

标签 python binary-search

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

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

最佳答案

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

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

相关文章:

java - 我的二分查找出了什么问题?

java - 二分查找给出了错误的输出 Java

java - 二分查找CompareTo Java

concurrency - 并发二值斩波算法

python - numpy search在切片上按字典顺序排序

python - 循环重置计数并覆盖文件

python - 常规 Python for 循环中的 If 子句

python - Py2Exe "The following modules are missing"

python - 我无法让 OpenCV 中的 CV2.waitKey 正常工作。运行 waitKey 后代码没有响应

Python 等同于 R poly() 函数?