`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` — 陣列二分演算法¶