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/

相关文章:

python - 比较运算符为 | 提供不同的值& 与 and or 相比 - Python

python - 如何在 Cython 中构建元组?

c++ - 显示所有匹配值的二进制搜索功能?

c# - 如何让二进制搜索方法返回 false?

java - 使用二进制搜索插入有序数组

python - 矩形没有出现在 opencv 中

python - 将多个字典附加到列表并转储到 json

python - 如何解决错误 :SDL_OpenAudio (2 channels, 44​​100 Hz):没有这样的音频设备

javascript - 二进制搜索代码

python - numpy.searchsorted 的性能在结构化数组上很差