搜索已排序列表？

Question

如何使用Pythonic的方式搜索或操作已排序的序列(sequence)?

- Basilevs

---

什么序列？还有，什么类型的搜索（二分等）？ - Alex Bliskovsky

我认为这个问题试图成为“规范”或“通用”，因此“序列”的含义可能是使用Python文档定义的sequence（即Python 2.x中的“有七种序列类型：字符串，Unicode字符串，列表，元组，bytearrays，缓冲区和xrange对象。”）。 - Trevor Boyd Smith

在Python中进行二分查找（又称折半查找） - Karl Knechtel

Answer 1

bisect是标准库的一部分 - 这是否是你正在寻找的类型？

- Daniel Roseman

---

那并没有解释如何在列表中搜索该值。 - Jean-François Fabre

从您提供的链接中：”bisect（）函数对于查找插入点很有用，但对于常见的搜索任务可能会变得棘手或笨拙。“ - MrMartin

@MrMartin，在已排序列表中查找插入点和执行“常规搜索任务”有什么区别？ - theonlygusti

@theonlygusti 我相信重点在于可能需要辅助函数，并且搜索通常需要找到所有匹配项，而不仅仅是第一个。 - MrMartin

这个答案中提供了解决方案。 - Basj

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模块的作者。

- GrantJ

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

- Paulo A. Ferreira

---

@Basilevs 这应该是被接受的答案 :) - Basj