`bisect` --- 数组二分查找算法¶

源代码： Lib/bisect.py

这个模块对有序列表提供了支持，使得他们可以在插入新数据仍然保持有序。对于长列表，如果其包含元素的比较操作十分昂贵的话，这可以是对更常见方法的改进。这个模块叫做 bisect 因为其使用了基本的二分（bisection）算法。源代码也可以作为很棒的算法示例（边界判断也做好啦！）

定义了以下函数：

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

在 a 中找到 x 合适的插入点以维持有序。参数 lo 和 hi 可以被用于确定需要考虑的子集；默认情况下整个列表都会被使用。如果 x 已经在 a 里存在，那么插入点会在已存在元素之前（也就是左边）。如果 a 是列表（list）的话，返回值是可以被放在 list.insert() 的第一个参数的。

返回的插入点 i 将数组 a 分成两半，使得 all(val < x for val in a[lo : i]) 在左半边而 all(val >= x for val in a[i : hi]) 在右半边。

key 指定带有单个参数的 key function 用来从数组的每个元素中提取比较键。为了支持搜索复杂记录，键函数不会被应用到 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)¶

Similar to bisect_left(), but returns an insertion point which comes after (to the right of) any existing entries of x in a.

返回的插入点 i 将数组 a 分成两半，使得左半边为 all(val <= x for val in a[lo : i]) 而右半边为 all(val > x for val in a[i : hi])。

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

如果 key 为 None，则将直接进行元素比较而不需要中间的函数调用。

在 3.10 版更改: 增加了 key 形参。

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

按照已排序顺序将 x 插入到 a 中。

This function first runs bisect_left() to locate an insertion point. Next, it runs the insert() method on a to insert x at the appropriate position to maintain sort order.

为了支持将记录插入到表中，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)¶

Similar to insort_left(), but inserting x in a after any existing entries of x.

This function first runs bisect_right() to locate an insertion point. Next, it runs the insert() method on a to insert x at the appropriate position to maintain sort order.

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

请记住 O(log n) 搜索是由缓慢的 O(n) 抛入步骤主导的。

在 3.10 版更改: 增加了 key 形参。

性能说明¶

当使用 bisect() 和 insort() 编写时间敏感的代码时，请记住以下概念。

二分法对于搜索一定范围的值是很高效的。对于定位特定的值，则字典的性能更好。
insort() 函数的时间复杂度为 O(n) 因为对数时间的搜索步骤被线性时间的插入步骤所主导。
The search functions are stateless and discard key function results after they are used. Consequently, if the search functions are used in a loop, the key function may be called again and again on the same array elements. If the key function isn't fast, consider wrapping it with functools.cache() to avoid duplicate computations. Alternatively, consider searching an array of precomputed keys to locate the insertion point (as shown in the examples section below).

参见

Sorted Collections is a high performance module that uses bisect to managed sorted collections of data.
SortedCollection recipe 使用 bisect 构建了一个功能完整的多项集类，拥有直观的搜索方法和对键函数的支持。所有键函数都是预先计算好的以避免在搜索期间对键函数的不必要的调用。

搜索有序列表¶

The above bisect functions are useful for finding insertion points but can be tricky or awkward to use for common searching tasks. The following five functions show how to transform them into the standard lookups for sorted lists:

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

例子¶

The bisect() function can be useful for numeric table lookups. This example uses bisect() to look up a letter grade for an exam score (say) based on a set of ordered numeric breakpoints: 90 and up is an 'A', 80 to 89 is a 'B', and so on:

>>> 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']

The bisect() and insort() functions also work with lists of tuples. The key argument can serve to extract the field used for ordering records in a table:

>>> 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` --- 数组二分查找算法¶