Python - bisect 模組介紹
在 Python 中，有一個內建的 bisect 模組提供了二元搜尋法的搜尋與維持排序狀態的函數。
在本文中，我們將會介紹 bisect 模組的用法。
bisect.bisect_left() 與 bisect.bisect_right()
bisect.bisect_left() 函數可以用來尋找目標元素在已排序的陣列中的插入點，如果有好幾個相同的元素，則會回傳最左邊的 index。bisect.bisect_right() 函數則是回傳最右邊的 index。
1
2
3
4
5
6
7
8
9
10import bisect
data = [1, 2, 3, 4, 5, 16, 32, 73, 85, 97]
print(bisect.bisect_left(data, 73)) # 7
print(bisect.bisect_right(data, 73)) # 8
print(bisect.bisect_left(data, 3)) # 2
print(bisect.bisect_right(data, 3)) # 3
print(bisect.bisect_left(data, 7)) # 5
print(bisect.bisect_right(data, 7)) # 5
bisect.insort_left() 與 bisect.insort_right()
bisect.insort_left() 函數可以用來將目標元素插入到已排序的陣列中並不會破壞其排序好的狀態，如果有好幾個相同的元素，則會插入到最左邊。bisect.insort_right() 函數則是插入到最右邊。1
2
3
4
5
6
7
8
9import bisect
data = [1, 2, 3, 4, 5, 16, 32, 73, 85, 97]
bisect.insort_left(data, 7)
print(data) # [1, 2, 3, 4, 5, 7, 16, 32, 73, 85, 97]
bisect.insort_right(data, 7)
print(data) # [1, 2, 3, 4, 5, 7, 7, 16, 32, 73, 85, 97]
bisect.bisect() 與 bisect.insort()
可以注意的是 bisect.bisect() 函數與 bisect.insort() 函數是 bisect.bisect_left() 與 bisect.insort_left() 的別名。1
2
3
4
5
6
7
8
9
10import bisect
data = [1, 2, 3, 4, 5, 16, 32, 73, 85, 97]
print(bisect.bisect(data, 73)) # 8
print(bisect.bisect(data, 3)) # 3
print(bisect.bisect(data, 7)) # 5
bisect.insort(data, 7)
print(data) # [1, 2, 3, 4, 5, 7, 16, 32, 73, 85, 97]
參考資料
如果你需要更多的資訊，可以參考官方文件。
https://docs.python.org/zh-tw/3/library/bisect.html
也可以直接閱讀他的原始碼。
https://github.com/python/cpython/blob/3.12/Lib/bisect.py