如何使用 Python 中的二分搜尋有效地檢查排序清單中的項目是否存在？

使用顯式項目存在檢查的Python 中的二分搜尋（二分）

Python bisect 模組提供執行二分搜尋的函數，例如bisect_left和bisect_right。但是，即使正在搜尋的項目不存在於清單中，這些函數也會傳回一個位置。對於僅需要某個項目存在或不存在的情況，需要更明確的檢查。

一種方法是使用 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

此函數採用排序清單 a、目標值 x 以及可選的搜尋下限和上限。它使用 bisect_left 來尋找 x 的插入點，然後檢查該位置的項目是否與目標相符。如果找到匹配項，函數將返回位置；否則，它會傳回 -1 來指示該項目不存在。

透過合併此明確檢查，您可以有效地確定排序清單中是否存在某個項目，而不會引入不必要的開銷或限制。

以上是如何使用 Python 中的二分搜尋有效地檢查排序清單中的項目是否存在？的詳細內容。更多資訊請關注PHP中文網其他相關文章！