高校情報Ⅰ　探索アルゴリズム（線形探索・二分探索）（5か月目第1週）

3.1 二分探索とは

二分探索（にぶんたんさく）は、高速の探索アルゴリズムです。
この方法を使う場合は、データがあらかじめ小さい順（または大きい順）に整列（ソート）されていることが条件になります💡

★手順
① 探索範囲の真ん中のデータを見る。
② 真ん中のデータが探したいデータでなければ、大小を比較する。
③ 探したいデータの方が大きければ後半に、小さければ前半に範囲を絞る。
④ ①～③を、データが見つかるか、探索範囲がなくなるまで繰り返す。

まず適当に真ん中あたりを開き、目的の単語がそのページより前にあるか後にあるかで、探す範囲を半分に絞り込んでいきますよね！

3.2 Pythonで二分探索

小さい順に整列済みのnumbers のリストでの二分探索をやってみます。

# Pythonの例：
小さい順に整列されたリスト
numbers = [10, 20, 30, 40, 50, 60, 70, 80, 90]
target = 70 # 探したい数字

left = 0 # 探索範囲の左端のインデックス（リストは1つめを0番目（インデックス0）と数える）
right = len(numbers) - 1 # 探索範囲の右端のインデックス（len()はリスト内の要素の個数）
found = False # 見つかったかどうかの旗

while left <= right:  # 探索範囲がある間、繰り返す
    mid = (left + right) // 2  # 探索範囲の真ん中のインデックスを計算（//は、小数点以下を切り捨てて、整数にする）
    print("チェック中:", numbers[mid])

    if numbers[mid] == target:  # 真ん中の値が探している数字だったら
        print(target, "をインデックス", mid, "で見つけました！")
        found = True
        break
    elif numbers[mid] < target:  # 真ん中の値より探している数字が大きい場合
        left = mid + 1  # 探索範囲を右半分に絞る
    else:  # 真ん中の値より探している数字が小さい場合
        right = mid - 1  # 探索範囲を左半分に絞る

# whileがすべて終わった後に実行される 
if not found:
    print(target, "は見つかりませんでした。")

# 出力結果
チェック中: 50 
チェック中: 70 
70 をインデックス 6 で見つけました！

最初に、10～90（インデックス0～8）の真ん中の 50 （インデックス4）を見て、探している 70 の方が大きいので後半の60～90（インデックス5～8）に絞った。
次に、60～90の真ん中 70 をみたら、探してる値だった。
この、60, 70, 80, 90（インデックス5～8）で要素が4つの真ん中は、mid = (left + right) // 2 のところが(5+8)//2になると、小数点以下切り捨て、ということで(5+8)÷2で6.5 ⇒6　ということで、インデックス6の70になって、探していた値が見つかった！ということです！

このように、どんどん範囲を狭めて効率的に探しています！

3.3 二分探索の長所と短所

■長所
・データ数が多くても、高速に探索できる。

■短所
・データがあらかじめ整列（ソート）されている必要がある。
・データの追加や削除が頻繁にあると、その都度整列し直す必要がある。