"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*，並維持順序。

   This function first runs "bisect_left()" to locate an insertion
   point. Next, it runs the "insert()" method on *a* to insert *x* at
   the appropriate position to maintain sort order.

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

   Keep in mind that the *O*(log *n*) search is dominated by the slow
   *O*(*n*) insertion step.

   在 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* 的後面（
   右邊）。

   This function first runs "bisect_right()" to locate an insertion
   point. Next, it runs the "insert()" method on *a* to insert *x* at
   the appropriate position to maintain sort order.

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

   Keep in mind that the *O*(log *n*) search is dominated by the slow
   *O*(*n*) insertion step.

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


效能考量
========

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

* 二分法在一段範圍的數值中做搜索的效率較佳，但若是要存取特定數值，使用
  字典的表現還是比較好。

* The *insort()* functions are *O*(*n*) because the logarithmic search
  step is dominated by the linear time insertion step.

* 搜索函式為無狀態的 (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)
