`bisect` — 数组二分算法¶

此模块提供支持，用于在无需每次插入后都对列表进行排序的情况下保持列表的有序性。对于包含开销很大的比较操作的长列表项，这可以改进线性搜索或频繁重新排序。

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

提供了以下函数

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

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

返回的插入点 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)¶

以排序顺序将 x 插入 a 中。

此函数首先运行 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)

`bisect` — 数组二分算法¶

性能说明¶

搜索排序列表¶

示例¶

目录

上一主题

下一主题

本页

bisect — 数组二分算法¶

性能说明¶

搜索排序列表¶

示例¶

`bisect` — 数组二分算法¶