`bisect` --- 陣列二分演算法 (Array bisection algorithm)¶

原始碼：Lib/bisect.py

這個模組維護一個已經排序過的 list ，當我們每次做完插入後不需要再次排序整個 list 。一個很長的 list 的比較操作很花費時間，為了改進這點，這個模組是其中一個常用的方法。這個模組被命名為 bisect 來自他使用一個基礎的 bisection 演算法實作。模組的原始碼是這個演算法的一個完善的實作（邊界條件已經是正確的了）。

此模組提供下面的函式：

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

在 a 當中找到一個位置，讓 x 插入後 a 仍然是排序好的。參數 lo 和 hi 用來指定 list 中應該被考慮的子區間，預設是考慮整個 list 。如果 a 裡面已經有 x 出現，插入的位置會在所有 x 的前面（左邊）。回傳值可以被當作 list.insert() 的第一個參數，但列表 a 必須先排序過。

回傳的插入位置 i 將陣列 a 分為兩半，使得 all(val < x for val in a[lo : i]) 都在左側且 all(val >= x for val in a[i : hi]) 都在右側。

key 可指定一個單一參數的 key function。函式將套用此 function 在陣列所有元素以得到比較值來計算順位。注意此 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)¶

類似 bisect_left()，但回傳的插入位置會在所有 a 當中的 x 的後面（右邊）。

回傳的插入位置 i 將陣列 a 分為兩半，使得 all(val <= x for val in a[lo : i]) 都在左側且 all(val > x for val in a[i : hi]) 都在右側。

key 可指定一個單一參數的 key function。函式將套用此 function 在陣列所有元素以得到比較值來計算順位。注意此 function 只會套用在陣列中的元素，不會套用在 x。

若 key 為 None，則排序順位將直接以陣列中元素值決定。

在 3.10 版的變更: 新增 key 參數。

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

將元素 x 插入 list a，並維持順序。

此函数会先运行 bisect_left() 来定位一个插入点。然后，它会在 a 上运行 insert() 方法在适当的位置插入 x 以保持排序顺序。

此函式只有在搜索時會使用 key 函式，插入時不會。

请记住 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 的後面（右邊）。

此函数会先运行 bisect_right() 来定位一个插入点。然后，它会在 a 上运行 insert() 方法在适当的位置插入 x 以保持排序顺序。

此函式只有在搜索時會使用 key 函式，插入時不會。

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

在 3.10 版的變更: 新增 key 參數。

效能考量¶

若在需要關注寫入時間的程式當中使用 bisect() 和 insort()，請特別注意幾個事項：

二分法在一段範圍的數值中做搜索的效率較佳，但若是要存取特定數值，使用字典的表現還是比較好。
insort() 函数的时间复杂度为 O(n) 因为对数时间的搜索步骤被线性时间的插入步骤所主导。
搜索函式為無狀態的 (stateless)，且鍵函式會在使用過後被丟棄。因此，如果搜索函式被使用於迴圈當中，鍵函式會不斷被重複呼叫於相同的 list 元素。如果鍵函式執行速度不快，請考慮將其以 functools.cache() 包裝起來以減少重複的計算。另外，也可以透過搜尋預先計算好的鍵列表 (array of precomputed keys) 來定位插入點（如下方範例所示）。

也參考

有序容器 (Sorted Collections) 是一個使用 bisect 來管理資料之有序集合的高效能模組。
SortedCollection recipe 使用二分法來建立一個功能完整的集合類別 (collection class) 並帶有符合直覺的搜索方法 (search methods) 與支援鍵函式。鍵會預先被計算好，以減少搜索過程中多餘的鍵函式呼叫。

搜尋一個已排序的 list¶

上面的 bisect functions 在找到數值插入點上很有用，但一般的數值搜尋任務上就不是那麼的方便。以下的五個函式展示了如何將其轉換成標準的有序列表查找函式：

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() 函式可用於數值表中的查找 (numeric table lookup)，這個範例使用 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() 函式也適用於內容為 tuples（元組）的 lists，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` --- 陣列二分演算法 (Array bisection algorithm)¶

效能考量¶

搜尋一個已排序的 list¶

範例¶

目錄

上個主題

下個主題

此頁面

bisect --- 陣列二分演算法 (Array bisection algorithm)¶

效能考量¶

搜尋一個已排序的 list¶

範例¶

`bisect` --- 陣列二分演算法 (Array bisection algorithm)¶