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)