在 Python 中使用排序列表：「bisect」模組的魔力

使用排序清單有時可能有點棘手。您需要在每次插入後維護清單的順序，並有效地搜尋其中的元素。二分搜尋是一種用於在排序清單中搜尋的強大演算法。雖然從頭開始實施並不太困難，但可能非常耗時。幸運的是，Python 提供了 bisect 模組，這使得處理排序清單變得更加容易。

什麼是二分查找？

二分搜尋是一種在排序數組中尋找目標值位置的演算法。想像一下您正在電話簿中搜尋一個名字。您可能不是從第一頁開始，而是從書的中間開始，並根據名稱按字母順序是大於還是小於中間的名稱來決定是在前半部分還是後半部分繼續搜索。二分查找以類似的方式進行操作：它以兩個指標開始，一個位於列表的開頭，另一個位於列表的末端。然後計算中間元素並與目標進行比較。

bisect 模組：簡化排序清單操作

雖然二分搜尋很有效，但每次都寫出實作可能很乏味。但是，如果您只需一行程式碼即可執行相同的操作呢？這就是 Python 的 bisect 模組的用武之地。 bisect 是 Python 標準庫的一部分，可協助您維護排序列表，而無需在每次插入後進行排序。它使用簡單的二分演算法來實現這一點。

bisect 模組提供了兩個關鍵函數：bisect 和 insort。 bisect 函數尋找應插入元素以保持清單排序的索引，而 insort 函數將元素插入清單中同時保持其排序順序。

使用二等分模組：一個實際範例

讓我們從導入模組開始：

import bisect

範例 1：將數字插入排序列表

假設我們有一個已排序的數字列表：

data = [1, 3, 5, 6, 8]

要在保持清單排序的同時插入新號碼，只需使用：

bisect.insort(data, 7)

執行此程式碼後，資料將如下所示：

[1, 3, 5, 6, 7, 8]

範例 2：尋找插入點

如果您只想找出數字將插入的位置而不實際插入怎麼辦？您可以使用 bisect_left 或 bisect_right 函數：

index = bisect.bisect_left(data, 4)
print(index)  # Output: 2

這告訴我們應該將數字 4 插入索引 2 處以保持清單有序。

範例 3：維護動態清單中的排序順序

假設您正在管理一個動態成長的列表，並且需要插入元素，同時確保其保持排序：

dynamic_data = []
for number in [10, 3, 7, 5, 8, 2]:
    bisect.insort(dynamic_data, number)
    print(dynamic_data)

這將在插入元素時輸出每一步的清單：

[10]
[3, 10]
[3, 7, 10]
[3, 5, 7, 10]
[3, 5, 7, 8, 10]
[2, 3, 5, 7, 8, 10]

範例 4：將 bisect 與自訂物件結合使用

假設您有一個自訂物件列表，例如元群組，並且您想要根據特定條件插入它們：

items = [(1, 'apple'), (3, 'cherry'), (5, 'date')]
bisect.insort(items, (2, 'banana'))
print(items)  # Output: [(1, 'apple'), (2, 'banana'), (3, 'cherry'), (5, 'date')]

或者您可能想要根據每個元組的第二個元素插入：

items = [('a', 10), ('b', 20), ('c', 30)]
bisect.insort(items, ('d', 25), key=lambda x: x[1])
print(items)  # Output: [('a', 10), ('b', 20), ('d', 25), ('c', 30)]

行動中的二分法：搜尋單字

二等分模組不限於數字；它對於搜尋字串、元組、字元等清單也很有用。
例如，要在排序清單中尋找單字：

def searchWord(dictionary, target):
    return bisect.bisect_left(dictionary, target)


dictionary = ['alphabet', 'bear', 'car', 'density', 'epic', 'fear', 'guitar', 'happiness', 'ice', 'joke']
target = 'guitar'

或尋找具有特定前綴的單字組中的第一個字：

def searchPrefix(dictionary, prefix):
    return bisect.bisect_left(dictionary, prefix), bisect.bisect_right(dictionary, prefix + 'z') # adding 'z' to the prefix to get the last word starting with the prefix
# bisect_rigth function will be discussed in a moment


dictionary = ['alphabet', 'bear', 'car', 'density', 'epic', 'fear', 'generator', 'genetic', 'genius', 'gentlemen', 'guitar', 'happiness', 'ice', 'joke']
prefix = 'gen'

但是，請記住 bisect_left 傳回應插入目標的索引，而不是目標是否存在於清單中。

bisect 和 insort 的變體

這個模組還包括右側變體：bisect_right 和 insort_right。如果元素已在清單中，這些函數將傳回插入元素的最右側索引。例如，如果目標在清單中，bisect_right 將傳回大於目標的第一個元素的索引，而 insort_right 將在該位置插入元素。

引擎蓋下平分

bisect 模組的強大之處在於它有效地實現了二分搜尋演算法。例如，當您呼叫 bisect.bisect_left 時，函數本質上會對清單執行二分搜尋以確定新元素的正確插入點。

以下是它的運作方式：

1. 初始化：函數以兩個指標lo和hi開始，它們代表列表內搜尋範圍的下限和上限。最初，lo 設定為列表的開頭（索引 0），hi 設定為列表的末尾（索引等於列表的長度）。但您也可以指定自訂 lo 和 hi 值以在清單的特定範圍內進行搜尋。

2. Bisection: Within a loop, the function calculates the midpoint (mid) between lo and hi. It then compares the value at mid with the target value you’re looking to insert.

3. Comparison:

* If the target is less than or equal to the value at `mid`, the upper bound (`hi`) is moved to `mid`.
* If the target is greater, the lower bound (`lo`) is moved to `mid + 1`.

1. Termination: This process continues, halving the search range each time, until lo equals hi. At this point, lo (or hi) represents the correct index where the target should be inserted to maintain the list's sorted order.

2. Insertion: For the insort function, once the correct index is found using bisect_left, the target is inserted into the list at that position.

This approach ensures that the insertion process is efficient, with a time complexity of O(log n) for the search and O(n) for the insertion due to the list shifting operation. This is significantly more efficient than sorting the list after each insertion, especially for large datasets.

bisect_left code example:

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    if key is None:
        while lo < hi:
            mid = (lo + hi) // 2
            if a[mid] < x:
                lo = mid + 1
            else:
                hi = mid
    else:
        while lo < hi:
            mid = (lo + hi) // 2
            if key(a[mid]) < x:
                lo = mid + 1
            else:
                hi = mid
    return lo

insort_left code example:

def insort_left(a, x, lo=0, hi=None, *, key=None):

    if key is None:
        lo = bisect_left(a, x, lo, hi)
    else:
        lo = bisect_left(a, key(x), lo, hi, key=key)
    a.insert(lo, x)

Conclusion

The bisect module makes working with sorted lists straightforward and efficient. The next time you need to perform binary search or insert elements into a sorted list, remember the bisect module and save yourself time and effort.

以上是在 Python 中使用排序列表：「bisect」模組的魔力的詳細內容。更多資訊請關注PHP中文網其他相關文章！