如何在 Python 中有效率地執行真/假二分查找？

Python 中的二分查找：改進的方法

在 Python 中，二分查找是透過 bisect 模組輕鬆執行的。但是，如果需要精確指示清單中某個項目的存在，則 bisect_left 和 bisect_right 函數可能不夠。

為了滿足這項需求，Python 函式庫不提供專為二分搜尋量身定制的專用函數明確的 True/False 輸出。因此，需要一個自訂解決方案。

以下程式碼片段定義了 binary_search 函數，該函數對排序列表 a 執行二分搜索，並在找到時返回目標項目 x 的索引。如果 x 不存在，則傳回 -1：

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  # Check if x is there

此函數利用 bisect_left 來決定 x 的插入點。如果 x 存在於清單中，它將位於該插入點。為了確認這一點，將插入點的值與 x 進行比較。如果它們匹配，則找到 x，並返回其索引。否則，x 不存在，並返回 -1 來指示這一點。

此自訂函數提供了一種簡潔高效的解決方案，用於執行二分搜索，並清楚地指示列表中項目是否存在，滿足原始問題中確定的需求。

以上是如何在 Python 中有效率地執行真/假二分查找？的詳細內容。更多資訊請關注PHP中文網其他相關文章！