Python 模組介紹 - bisect

談到插入(insert)元素到已排序串列(list) ，最暴力的方法就是每次插入元素後直接排序：

>>> a = [1, 2, 3, 4]
>>> a.insert(0, 5)
>>> a
[5, 1, 2, 3, 4]
>>> a.sort()
>>> a
[1, 2, 3, 4, 5]

不過隨著串列越來越長，每次插入元素後再進行排序的方式，將會越來越慢，甚至造成大量不必要的運算，這時可以利用 Python 內建模組 bisect ，透過二元搜尋的方式幫我們插入元素到串列之中，如此一來該串列就不需要在新增元素後進行排序。

p.s bisect 只能運用在已排序過的串列(list)

本文環境 #

• Python 3.7

bisect, bisect_left, bisect_right #

先前提到 bisect 模組能夠透過二元搜尋的方式，插入元素到串列之中。

在此之前，可以先認識 bisect.bisect_left 函式，該函式可以找出元 素的插入索引位置，例如以下使用 bisect.bisect_left 找出整數 3 在串列 [2, 4, 6] 的插入索引為 1 ，也就是串列的第 2 個位置：

>>> import bisect
>>> a = [2, 4, 6]
>>> bisect.bisect_left(a, 3)
1

接著按照該索引 1 將整數 3 插入至串列 a 後，該串列依然維持已排序的狀態：

>>> a.insert(1, 3)
>>> a
[2, 3, 4, 6]

bisect.bisect_left 還有個特性，當串列中含有重複的元素時，如果想再插入一個相同的元素時，例如在 [2, 2, 4, 4, 6, 6, 8, 8] 中再插入 1 個整數 4 ， bisect.bisect_left 所回傳的串列索引位置 2 會確保該位置左邊都小於 < 欲插入的值，而該位置右邊的所有值都大於等於 >= 欲插入的值，也就是 [2, 2, 4, 4, 6, 6, 8, 8] 會被分為 [2, 2] 與 [4, 4, 6, 6, 8, 8] ，而索引位置 2 就在重複元素 4 的左邊，這也就是 bisect.bisect_left 會有 _left 的由來：

>>> import bisect
>>> a = [2, 2, 4, 4, 6, 6, 8, 8]
>>> bisect.bisect_left(a, 4)
2

p.s. bisect.bisect_left 可以想像是當有重複元素時，再插入 1 個相同元素的話，該元素會被排到第 1 個

有 bisect.bisect_left 的話，當然就會有 bisect.bisect_right ，也等同於 bisect.bisect ， bisect.bisect_right 所回傳的串列索引位置 2 會確保該位置左邊都小於等於 <= 欲插入的值，而該位置右邊的所有值都大於 > 欲插入的值，例如在 [2, 2, 4, 4, 6, 6, 8, 8] 中再插入 1 個整數 4 ， bisect.bisect_right 所回傳的串列索引位置 4 會將 [2, 2, 4, 4, 6, 6, 8, 8] 分為 [2, 2, 4, 4] 與 [6, 6, 8, 8] ，而索引位置 4 就在重複元素 4 的右邊，這也就是 bisect.bisect_right 會有 _right 的由來

>>> import bisect
>>> a = [2, 2, 4, 4, 6, 6, 8, 8]
>>> bisect.bisect(a, 4)
4

p.s. bisect.bisect_right 可以想像是當有重複元素時，再插入 1 個相同元素的話，該元素會被排到最後

>>> import bisect
>>> a = [2, 2, 4, 4, 6, 6, 8, 8]
>>> bisect.bisect_right(a, 4)
4

insort, insort_right, insort_left #

了解 bisect, bisect_left, bisect_right 的作用之後， insort, insort_right, insort_left 等函式就很好理解了。

insort, insort_right, insort_left 會直接插入元素到串列之中：

>>> import bisect
>>> a = [2, 4, 6, 8]
>>> bisect.insort_left(a, 4)
>>> a
[2, 4, 4, 6, 8]

>>> import bisect
>>> a = [2, 4, 6, 8]
>>> bisect.insort_left(a, 4)
>>> a
[2, 4, 4, 6, 8]

額外用途 #

有些時候可能會寫出類似以下多種 if 的判斷式：

price = 80

if price >= 100:
    print('偏貴')
elif price >= 90:
    print('合理')
elif price >= 80:
    print('便宜')
elif price >= 70:
    print('超便宜')
else:
    print('不合理')

不過上述形式的程式碼也可以用 bisect 進行改寫：

from bisect import bisect


price_thresholds = [70, 80, 90, 100]
results = ['不合理', '超便宜', '便宜', '合理', '偏貴']

idx = bisect(price_thresholds, 80)
print(results[idx])

以上就是 bisect 模組的介紹。

Happy Coding!

References #

https://docs.python.org/3/library/bisect.html