搜索排序列表？

Question

搜索或操作排序的sequence的Pythonic方法是什么

Answer 1

bisect是标准库的一部分--这就是你要找的东西吗？

Answer 2

值得注意的是，有两个高质量的Python库用于维护排序列表，它们也实现了快速搜索：sortedcontainers和blist。当然，使用这些依赖于您在列表中插入/删除元素的频率以及需要搜索的频率。这些模块中的每个模块都提供了一个SortedList类，该类可以有效地维护排序顺序中的项。

来自SortedList的文档：

L.bisect_left(value)
    Similar to the bisect module in the standard library, this returns
    an appropriate index to insert value in L. If value is already present
    in L, the insertion point will be before (to the left of) any existing
    entries.

L.bisect(value)
    Same as bisect_left.

L.bisect_right(value)
    Same as bisect_left, but if value is already present in L, the
    insertion point will be after (to the right of) any existing entries.

这两种实现都使用二进制搜索来查找给定值的正确索引。有一个performance comparison页面可以在两个模块之间进行选择。

免责声明:我是sortedcontainers模块的作者。

Answer 3

Python：

def find_elem_in_sorted_list(elem, sorted_list):
    # https://docs.python.org/3/library/bisect.html
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(sorted_list, elem)
    if i != len(sorted_list) and sorted_list[i] == elem:
        return i
    return -1