バイナリ検索でPythonリストの要素のインデックスを見つける方法

リスト要素のインデックスをバイナリサーチを使用して検索するには、次の手順に従います。

1. 連続した要素を持つリスト、および探したい要素を引数とする二分探索関数を定義します。この関数は要素のリスト内の要素のインデックスを戻り値としますが、要素が存在しない場合は-1を戻り値とします。
2. 関数のなかで、左境界は0、右境界はリストの長さから1を引いて初期化します。
3. mid = （left + right）/ 2と、中央のインデックスの値を計算します。
4. 中間要素が検索要素と等しい場合は、中間要素のインデックスを返す。
5. 中央の要素が検索する要素より大きい場合、右端をmid – 1に更新する。
6. 中央要素が検索要素未満の場合は、左境界をmid + 1に更新する。
7. 要素が見つからなかった場合は、-1 を返します。

検索したいリスト要素のインデックスを探し出すために２分探索法を使用する、サンプルコードを以下に示します。

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

# 示例输入和输出
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 6
index = binary_search(arr, target)
print(index)  # 输出: 5

上の例では、binary_search関数を呼び出して、リストarr内の要素targetのインデックスを検索し、結果を出力します。