Python - bisect 模組介紹

Posted on

在 Python 中，有一個內建的 bisect 模組提供了二元搜尋法的搜尋與維持排序狀態的函數。
在本文中，我們將會介紹 bisect 模組的用法。

bisect.bisect_left() 與 bisect.bisect_right()

bisect.bisect_left() 函數可以用來尋找目標元素在已排序的陣列中的插入點，如果有好幾個相同的元素，則會回傳最左邊的 index。
bisect.bisect_right() 函數則是回傳最右邊的 index。image 106

1
2
3
4
5
6
7
8
9
10
import 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
9
import 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
10
import 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

相關文章