如何在 Python 中有效率地實現二分查找來檢查專案是否存在？

Python中的二分搜尋（折半查找）

Python提供了實現二分搜尋（也稱為折半查找）的函式庫函數，用於在排序清單或元組中尋找項目。不過，這些函數在項未找到時仍會傳回一個位置。

為了解決這個問題並僅檢測項是否存在，一種方法是使用bisect.bisect_left()函數找到插入位置，然後檢查該位置處的項是否與目標項相等。然而，這可能很繁瑣，還需要在數字大於清單中最大數字時進行邊界檢查。

考慮到記憶體消耗，問題中提出了使用字典作為替代方案的建議。然而，這可能需要大約兩倍的記憶體需求。

因此，可以使用自訂程式碼實現二分搜尋來解決此問題：

from bisect import bisect_left

def binary_search(a, x, lo=0, hi=None):
    if hi is None: hi = len(a)
    pos = bisect_left(a, x, lo, hi)                 # find insertion position
    return pos if pos != hi and a[pos] == x else -1  # don't walk off the end

此函數使用bisect_left()函數來尋找插入位置，該位置指示目標項存在時的位置，或指示其不在時超出範圍的位置。檢查該位置處的項是否與目標項相等，可以確定目標項是否存在。

以上是如何在 Python 中有效率地實現二分查找來檢查專案是否存在？的詳細內容。更多資訊請關注PHP中文網其他相關文章！