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

原始碼：Lib/bisect.py

---

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

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

備註

The functions in this module are not thread-safe. If multiple threads concurrently use bisect functions on the same sequence, this may result in undefined behaviour. Likewise, if the provided sequence is mutated by a different thread while a bisect function is operating on it, the result is undefined. For example, using insort_left() on the same list from multiple threads may result in the list becoming unsorted.

此模組提供下面的函式：

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() 於