bisect — 数组二分查找算法

源代码： Lib/bisect.py

---

此模块提供了维护列表排序顺序的支持，而无需在每次插入后对列表进行排序。对于具有昂贵比较操作的长项目列表，这可以比线性搜索或频繁重新排序有所改进。

该模块之所以被称为 bisect 是因为它使用基本的二分查找算法来完成其工作。与搜索特定值的其他二分查找工具不同，此模块中的函数旨在查找插入点。因此，这些函数永远不会调用 __eq__() 方法来确定是否已找到值。相反，这些函数只调用 __lt__() 方法，并将返回数组中两个值之间的插入点。

提供以下函数

bisect.bisect_left(a, x, lo=0, hi=len(a), *, key=None)

查找在 a 中为 x 维持排序顺序的插入点。参数 lo 和 hi 可用于指定应考虑的列表子集；默认情况下使用整个列表。如果 x 已经存在于 a 中，则插入点将在任何现有条目之前（左侧）。返回值适合用作 list.insert() 的第一个参数，前提是 a 已经排序。

返回的插入点 ip 将数组 a 分为两个切片，使得左切片的 all(elem < x for elem in a[lo : ip]) 为真，右切片的 all(elem >= x for elem in a[ip : hi]) 为真。

key 指定一个单参数的键函数，用于从数组中的每个元素提取比较键。为了支持搜索复杂的记录，键函数不应用于 x 值。

如果 key 为 None，则直接比较元素，不调用键函数。

在 3.10 版本中变更: 添加了 key 参数。

bisect.bisect_right(a, x, lo=0, hi=len(a), *, key=None)

bisect.bisect(a, x, lo=0, hi=len(a), *, key=None)

与 bisect_left() 类似，但返回插入点，该插入点位于 a 中任何现有 x 条目之后（右侧）。

返回的插入点 ip 将数组 a 分为两个切片，使得左切片的 all(elem <= x for elem in a[lo : ip]) 为真，右切片的 all(elem > x for elem in a[ip : hi]) 为真。

在 3.10 版本中变更: 添加了 key 参数。

bisect.insort_left(a, x, lo=0, hi=len(a), *, key=None)

按排序顺序在 a 中插入 x。

此函数首先运行 bisect_left() 来定位插入点。接下来，它在 a 上运行 insert() 方法，以在适当的位置插入 x 以保持排序顺序。

为了支持在表中插入记录，key 函数（如果有）应用于搜索步骤的 x，但不应用于插入步骤。

请记住，O(log n) 搜索被缓慢的 O(n) 插入步骤所主导。

在 3.10 版本中变更: 添加了 key 参数。

bisect.insort_right(a, x, lo=0, hi=len(a), *, key=None)

bisect.insort(a, x, lo=0, hi=len(a), *, key=None)

与 insort_left() 类似，但在 a 中任何现有 x 条目之后插入 x。

此函数首先运行 bisect_right() 来定位插入点。接下来，它在 a 上运行 insert() 方法，以在适当的位置插入 x 以保持排序顺序。

为了支持在表中插入记录，key 函数（如果有）应用于搜索步骤的 x，但不应用于插入步骤。

请记住，O(log n) 搜索被缓慢的 O(n) 插入步骤所主导。

在 3.10 版本中变更: 添加了 key 参数。

性能注意事项

在使用 bisect() 和 insort() 编写对时间敏感的代码时，请记住以下几点

• 二分法对于搜索值范围是有效的。对于定位特定值，字典的性能更高。

• insort() 函数是 O(n) 的，因为对数搜索步骤会被线性时间插入步骤所主导。

• 搜索函数是无状态的，并在使用后丢弃键函数的结果。因此，如果在循环中使用搜索函数，则可能会对相同的数组元素一次又一次地调用键函数。如果键函数速度不快，请考虑使用 functools.cache() 对其进行包装，以避免重复计算。或者，考虑搜索预先计算的键数组来定位插入点（如下面的示例部分所示）。

另请参阅

• Sorted Collections 是一个高性能模块，它使用 bisect 来管理排序的数据集合。

• SortedCollection 配方使用 bisect 构建一个功能齐全的集合类，它具有直接的搜索方法并支持键函数。预先计算键以避免在搜索期间不必要地调用键函数。

搜索排序列表

上面的 bisect 函数 对于查找插入点很有用，但对于常见的搜索任务，使用起来可能很棘手或笨拙。以下五个函数演示了如何将它们转换为排序列表的标准查找

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

def find_lt(a, x):
    'Find rightmost value less than x'
    i = bisect_left(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_le(a, x):
    'Find rightmost value less than or equal to x'
    i = bisect_right(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_gt(a, x):
    'Find leftmost value greater than x'
    i = bisect_right(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

def find_ge(a, x):
    'Find leftmost item greater than or equal to x'
    i = bisect_left(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

示例

bisect() 函数可用于数值表查找。此示例使用 bisect() 基于一组有序的数字断点来查找考试分数的字母等级（例如）：90 及以上为“A”，80 到 89 为“B”，依此类推。

>>> def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
...     i = bisect(breakpoints, score)
...     return grades[i]
...
>>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
['F', 'A', 'C', 'C', 'B', 'A', 'A']

bisect() 和 insort() 函数也适用于元组列表。 key 参数可以用于提取用于在表格中排序记录的字段。

>>> from collections import namedtuple
>>> from operator import attrgetter
>>> from bisect import bisect, insort
>>> from pprint import pprint

>>> Movie = namedtuple('Movie', ('name', 'released', 'director'))

>>> movies = [
...     Movie('Jaws', 1975, 'Spielberg'),
...     Movie('Titanic', 1997, 'Cameron'),
...     Movie('The Birds', 1963, 'Hitchcock'),
...     Movie('Aliens', 1986, 'Cameron')
... ]

>>> # Find the first movie released after 1960
>>> by_year = attrgetter('released')
>>> movies.sort(key=by_year)
>>> movies[bisect(movies, 1960, key=by_year)]
Movie(name='The Birds', released=1963, director='Hitchcock')

>>> # Insert a movie while maintaining sort order
>>> romance = Movie('Love Story', 1970, 'Hiller')
>>> insort(movies, romance, key=by_year)
>>> pprint(movies)
[Movie(name='The Birds', released=1963, director='Hitchcock'),
 Movie(name='Love Story', released=1970, director='Hiller'),
 Movie(name='Jaws', released=1975, director='Spielberg'),
 Movie(name='Aliens', released=1986, director='Cameron'),
 Movie(name='Titanic', released=1997, director='Cameron')]

如果键函数开销很大，可以通过搜索预先计算的键列表来查找记录的索引，从而避免重复的函数调用。

>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
>>> data.sort(key=lambda r: r[1])       # Or use operator.itemgetter(1).
>>> keys = [r[1] for r in data]         # Precompute a list of keys.
>>> data[bisect_left(keys, 0)]
('black', 0)
>>> data[bisect_left(keys, 1)]
('blue', 1)
>>> data[bisect_left(keys, 5)]
('red', 5)
>>> data[bisect_left(keys, 8)]
('yellow', 8)