Python で二分検索を使用して、ソートされたリスト内の項目の存在を効率的に確認するにはどうすればよいですか?

明示的な項目存在チェックを使用した Python の二分検索 (二分)

Python の bisect モジュールは、bisect_left などの二分検索を実行するための関数を提供しますそしてbisect_right。ただし、これらの関数は、検索対象の項目がリストに存在しない場合でも位置を返します。項目の有無のみが必要な場合は、より明示的なチェックが必要です。

1 つのアプローチは、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 中国語 Web サイトの他の関連記事を参照してください。