"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()" 於
   *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)
   ...     i = bisect([60, 70, 80, 90], score)
   ...     return "FDCBA"[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')
   ... ]

   >>> # 找到 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')

   >>> # 插入一部電影並保持排序
   >>> 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)
