この Python 二分探索関数は要素を見つけますか?

Python の二分探索 (二分法)

ソートされたリストまたはタプルに要素が存在するかどうかを判断することは、プログラミングにおける一般的なタスクです。 Python は二分検索用の bisect モジュールを提供しますが、その bisect_left 関数と bisect_right 関数は、項目が見つからない場合でも位置を返します。このニーズに対処するために、明示的にブール値を返すバイナリ検索の Python 実装が導入されました。

提案されたソリューション

binary_search 関数は、並べ替えられたリスト 'a' を受け取ります。 、検索する要素「x」、およびオプションの検索範囲の開始位置と終了位置「lo」と「hi」。 bisect モジュールの bisect_left 関数を使用して、リスト 'a' 内の 'x' の挿入ポイント 'pos' を見つけます。

'pos' が 'hi' より小さく、要素が 'pos にある場合' が 'x' に等しい場合、'x' が見つかり、リスト内のその位置のインデックスとして 'pos' が返されます。ただし、'pos' がリストの最後に達した場合 (つまり、'pos' が 'hi' に等しい)、'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  # don't walk off the end

使用例

たとえば、並べ替えられたリスト 'a' と検索対象の要素 'x' が与えられた場合、 binary_search 関数は次のように使用できます:

result = binary_search(a, x)

if result == -1:
    print("Element not found")
else:
    print("Element found at index", result)

この簡潔な Python 関数は、二分検索の単純さと効率を維持しながら、ソートされたリスト内の要素の存在をチェックする二分検索を実行する便利な方法を提供します。

以上がこの Python 二分探索関数は要素を見つけますか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。