Day 96二分探索を実装する

2026-05-31 JST ・ 難易度: 中級 ・ カテゴリ: アルゴリズム

Pythonコード

1def binary_search(arr, target):2    low, high = 0, len(arr) - 13    while low <= high:4        mid = (low + high) // 25        if arr[mid] == target:6            return mid7        elif arr[mid] < target:8            low = mid + 19        else:10            high = mid - 111    return -112 13target = 514arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]15arr.sort()16result = binary_search(arr, target)17if result != -1:18    print(f'{target}はインデックス{result}にあります')19else:20    print(f'{target}は見つかりませんでした')

ここに出力が表示されます。

解説

• 行1〜3: 二分探索を行う関数binary_searchを定義します。ここでは、探索対象の配列arrと探索する値targetを引数として受け取ります。lowとhighは探索範囲の開始と終了を表します。len()関数は、配列の要素数（長さ）を返す関数です。
• 行4〜6: whileループ内で、探索範囲の中央のインデックスmidを計算します。ここで、midは整数でなければならないため、//で整数除算を行います。midの値とtargetの値を比較して、探索範囲を絞り込みます。
• 行7〜10: targetが見つかった場合、インデックスを返します。targetが見つからなかった場合、-1を返します。sort()関数は、配列の要素を昇順に並べ替える関数です。
• 行11〜14: 探索対象の配列arrと探索する値targetを定義します。ここでは、arrを昇順に並べ替えてから二分探索を行います。
• 行15: sort()関数は、配列の要素を昇順に並べ替える関数です。
• 行18〜20: print()関数は、画面に文字や値を表示する関数です。

次に試してみよう

• 二分探索の対象となる配列をランダムに生成し、探索する値もランダムに生成してみましょう。
• 二分探索のアルゴリズムを図示してみましょう。
• 二分探索の時間計算量を考えてみましょう。