搜索排序列表？

Question

什么是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.

两种实现都使用二进制搜索来查找给定值的正确索引.有一个性能比较页面,用于在两个模块之间进行选择.

免责声明:我是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