項目の存在を確認するために Python で二分検索を効率的に実装するにはどうすればよいですか?

Python の二分検索 (ハロー検索)

Python は、二分検索 (二分検索とも呼ばれます) を実装するためのライブラリ関数を提供します。ソートされたリストまたはタプル内の項目。ただし、項目が見つからない場合でも、これらの関数は位置を返します。

この問題を解決し、項目が存在するかどうかのみを検出するには、bisect.bisect_left() 関数を使用して挿入位置を見つけ、その位置にある項目がターゲット項目と等しいかどうかを確認する方法があります。 。ただし、これは面倒な場合があり、数値がリスト内の最大の数値よりも大きい場合には境界チェックも必要になります。

メモリを消費するため、質問では代替として辞書が提案されています。ただし、これには約 2 倍のメモリ要件が必要になる場合があります。

したがって、この問題は、カスタム コードを使用して二分探索を実装することで解決できます。

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 中国語 Web サイトの他の関連記事を参照してください。