談到插入(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.bisectbisect.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