`bisect` — 数组二分算法¶

本模块支持维护一个已排序的列表，而无需在每次插入后都重新排序。对于包含大量元素且比较操作耗时较长的列表，这比线性搜索或频繁重排更有效率。

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

备注

此模块中的函数不是线程安全的。如果多个线程并发地对同一个序列使用 bisect 函数，可能会导致未定义的行为。同样，如果在 bisect 函数操作期间，提供的序列被另一个线程修改，结果也是未定义的。例如，在多个线程中对同一个列表使用 insort_left() 可能会导致列表变得无序。

提供了以下函数：

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)¶

将 x 插入到 a 中，并保持 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() 类似，但将 x 插入到 *a* 中任何已有 *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 recipe 使用 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` — 数组二分算法¶