Python Bisect模塊示例

當需要在有序列表中高效插入元素並保持順序時應使用bisect 模塊，1. bisect.bisect_left(list, value) 返回應插入位置，相同值插左邊；2. bisect.bisect_right(list, value) 或bisect.bisect() 返回插入位置，相同值插右邊；3. bisect.insort_left(list, value) 將value 插入左邊位置；4. bisect.insort_right(list, value) 或bisect.insort() 插入右邊位置；示例中使用bisect.insort(scores, 77) 將成績77 插入有序列表並保持順序，插入重複值75 時默認插在已有75 後面，若用insort_left 則插在前面；通過bisect.bisect_left(scores, 75) 可僅獲取插入位置而不實際插入，可用於實現二分查找，如定義binary_search 函數查找某值是否存在；使用bisect 時列表必須預先排序，查找位置時間複雜度為O(log n)，但插入因元素移動為O(n)，頻繁插入場景可考慮heapq 或sortedcontainers 更高效，該模塊在處理有序數據插入與查找時非常實用，尤其適用於排行榜、時間序列數據等場景。

Python 的bisect模塊提供了一種在有序列表中插入元素並保持列表有序的高效方法。它使用二分查找算法，因此比每次插入後排序更高效。下面是一個實用的示例，幫助你理解如何使用bisect 。

? 什麼時候用bisect？

當你維護一個有序列表，並且需要頻繁插入新值但仍保持順序時， bisect非常有用，比如：

• 維護排行榜
• 插入時間序列數據
• 實現二分查找邏輯

? 常用函數說明

bisect模塊主要有兩個核心函數：

• bisect.bisect_left(list, value)
  返回value應該插入的位置，如果有相同值，插在左邊。

• bisect.bisect_right(list, value)或bisect.bisect()
  返回插入位置，相同值插在右邊。

  

• bisect.insort_left(list, value)
  直接將value插入到左邊位置，保持有序。

• bisect.insort_right(list, value)或bisect.insort()
  插入到右邊位置。

? 實際例子：維護一個有序成績列表

import bisect

# 初始有序的成績列表scores = [65, 70, 75, 80, 85]

# 插入新成績，保持有序bisect.insort(scores, 77)
print(scores) # [65, 70, 75, 77, 80, 85]

bisect.insort(scores, 75)
print(scores) # [65, 70, 75, 75, 77, 80, 85] —— 75 插在已有75 後面（insort 默認是right）

# 如果想插在左邊bisect.insort_left(scores, 75)
print(scores) # [65, 70, 75, 75, 75, 77, 80, 85]

? 查找插入位置而不實際插入

有時候你只想知道該插在哪，不立即插入：

 pos = bisect.bisect_left(scores, 75)
print(f"75 應該插入在位置{pos}") # 輸出2 或3，取決於已有幾個75

這個可以用來實現二分查找，比如查找某個值是否存在：

 def binary_search(arr, x):
    i = bisect.bisect_left(arr, x)
    if i != len(arr) and arr[i] == x:
        return i # 找到了，返回索引return -1 # 未找到print(binary_search(scores, 77)) # 輸出索引，比如5
print(binary_search(scores, 99)) # -1，沒找到

? 小貼士

• 列表必須預先排序，否則bisect行為不可預測。
• insort系列函數插入時時間複雜度是O(n)，因為列表移動元素；但查找位置是O(log n)。
• 對於頻繁插入的場景，考慮是否用heapq或sortedcontainers （第三方）更高效。

基本上就這些。 bisect不復雜，但在處理有序數據時非常實用，尤其配合二分查找或插入場景。

以上是Python Bisect模塊示例的詳細內容。更多資訊請關注PHP中文網其他相關文章！