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

這個模組維護一個已經排序過的 list ，當我們每次做完插入後不需要再次排序整個 list 。一個很長的 list 的比較操作很花費時間，可以透過線性搜索或頻繁地詢問來改善。

這個模組被稱為 bisect 是因為它使用基本二分演算法來完成其工作。不像其它搜尋特定值的二分法工具，本模組中的函式旨在定位插入點。因此，這些函式永遠不會呼叫 __eq__() 方法來確認是否找到一個值。相反地，這些函式只呼叫 __lt__() 方法，並在陣列中的值回傳一個插入點。

此模組提供下面的函式：

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 必須先排序過。

回傳的插入點 ip 將陣列 a 劃分為左右兩個切片，使得對於左切片而言 all(elem < x for elem in a[lo : ip]) 為真，對於右切片而言 all(elem >= x for elem in a[ip : 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 的後面（右邊）。

回傳的插入點 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 插入 list a，並維持順序。

此函式先使用 bisect_left() 搜索插入位置，接著用 insert() 於 a 以將 x 插入，並維持添加元素後的順序。

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

注意雖然搜索是 O(log n)，但插入是 O(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() 搜索插入位置，接著用 insert() 於 a 以將 x 插入，並維持添加元素後的順序。

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

注意雖然搜索是 O(log n)，但插入是 O(n)，因此此函式整體時間複雜度是 O(n)。

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

效能考量¶

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

二分法在一段範圍的數值中做搜索的效率較佳，但若是要存取特定數值，使用字典的表現還是比較好。
insort() 函式的複雜度為 O(n)，因為對數搜尋是以線性時間的插入步驟所主導 (dominate)。
搜索函式為無狀態的 (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)¶