Last Updated on 2022-11-26 by Clay
bisect 是一個 Python 的內建模組，其主要功能是維持一個排序後的 List 順序，讓該 List 在進行插入（insert）操作後無需重新排序整個 List。
很多人在寫題目、製作某項功能時可能都會有這樣的經驗：
當我們想要維持某個陣列中數值的順序，但是系統又有著需要不斷添加新的數值進入該陣列的需求，所以我們就很直覺地、無視效能地一次次重新排序陣列。
當然，這樣的操作在較長陣列中的效能是毀滅性的。而 bisect 就是基於這樣一個 bisection 的演算法去實作的。
bisect 使用方法
bisect.bisect_left(a, x, lo=0, hi=len(a), *, key=None)
參數意義如下：
a是一組排序後的陣列x是我們欲插入之值lo是陣列判斷的起始點，預設為 0hi是陣列判斷的結束點，預設為陣列長度key在 Python3.10 以後新增，你可以將希望判斷的比較方式寫成 key function 來使用。如果為 None，則預設是以陣列中的值大小進行比較
來看段範例程式碼：
# coding: utf-8
import bisect
def main() -> None:
arr = [1, 2, 5, 5, 6, 8]
insert_val = 3
print(bisect.bisect_left(arr, insert_val))
if __name__ == "__main__":
main()
Output:
2
我們會發現，在陣列 [1, 2, 5, 5, 6, 8] 中，如果要插入 3 這個數值，我們確實要插入在索引 2 的位置才不會讓排序亂掉。
除此之外，還有另外一個函式 bisect_right()。它又跟 bisect_left() 有什麼差異呢？
bisect.bisect_right(a, x, lo=0, hi=len(a), *, key=None)
就參數上來看，這兩個函式簡直一模一樣。唯一的區別是一個是優先返回最左邊的可能插入點、另一個則是優先返回最右邊的可能插入點。
以程式來看就很明顯：
# coding: utf-8
import bisect
def main() -> None:
arr = [1, 2, 5, 5, 6, 8]
insert_val = 5
print(f"bisect_left(): {bisect.bisect_left(arr, insert_val)}")
print(f"bisect_right(): {bisect.bisect_right(arr, insert_val)}")
if __name__ == "__main__":
main()
Output:
bisect_left(): 2
bisect_right(): 4
現在就可以很明顯看出差異。因為 5 這個數值無論放在陣列中連續個 5 中任何一個位置都行，但是一個會優先返回左邊的索引、一個則是返回最右邊的索引。
bisect.insort_left(a, x, lo=0, hi=len(a), *, key=None)
這個函式就不再是搜索而已，而是直接幫你把數值插入（insert）陣列中、並且不會打亂順序。（當然，也有 insort_right() 和 insort() 這兩個函式）
# coding: utf-8
import bisect
def main() -> None:
# Init
arr = [1, 2, 5, 6, 8]
# Insert
bisect.insort_left(arr, 9)
bisect.insort_left(arr, 4)
bisect.insort_left(arr, 7)
bisect.insort_left(arr, 3)
# Show
print(f"arr: {arr}")
if __name__ == "__main__":
main()
Output:
arr: [1, 2, 3, 4, 5, 6, 7, 8, 9]
你會發現插入新的數值並不會打亂已經排序後的陣列。