搜索已排序的列表？

Question

在Python中，有什么好的方法可以搜索或处理已经排好序的序列呢？

Answer 1

值得注意的是，有几个高质量的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 2

bisect 是 Python 自带的一个库，你是不是在找这种东西呢？

Answer 3

Python:

import bisect

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

def in_sorted_list(elem, sorted_list):
    i = bisect.bisect_left(sorted_list, elem)
    return i != len(sorted_list) and sorted_list[i] == elem

L = ["aaa", "bcd", "hello", "world", "zzz"]
print(find_in_sorted_list("hello", L))  # 2
print(find_in_sorted_list("hellu", L))  # -1
print(in_sorted_list("hellu", L))       # False

搜索已排序的列表？

3 个回答

撰写回答