Pythonでアルゴリズム「二分探索」：if文による条件分岐がキモであることが分かりました

Pythonでアルゴリズム「二分探索」の続きです。前回は、「二分探索」とは何か、その最初のステップをご紹介しました。今回は、Pythonでのコードを考えてみることにしましょう。

絵で見る「二分探索」

しかし、その前に、前回記事の補足です。二分探索の仕組みをさらにビジュアル化しました。これで、もっと分かりやすくなるかしらん🤔

二分探索のイメージ

1. 最初のループで、「真ん中の値」＜「目標の値」であることが分かりました。「真ん中の値」より小さい値は、探索対象から外れます。

2. 第2回目のループでは、「目標の値」＜「真ん中の値」であることが分かりました。「真ん中の値」より大きい値は、探索対象から外れます。

3. 第3回目のループで、「真ん中の値」＜「目標の値」であることが分かりました。「真ん中の値」より小さい値は、探索対象から外れます。

4. 第4回目のループで、「真ん中の値」＝「目標の値」であることが分かりました。目標の値の場所を特定できました！Yey😄

どんどんと探索対象が少なくなっていく様子が見て取れます。「二分探索」はこのように計算量を減らしていくアルゴリズムなんですね！

プログラムにするとこうなる

では、Pythonで「二分探索」のコードを書いてみましょう！完成形のサンプルは、次の通りです。

「なんか、前出のプログラムよりも、だいぶ長くなってきましたね…。😭」

確かに、そうですね…。しかし！分解して見ていけばきっと大丈夫！私の人生訓は、「困難は分割せよ」（by デカルト先生）です。ということで、私たちもプログラムをちまちま分割してみましょう🙂。

とはいえ、今日は、消化不良になるといけないので、コード全体をうす～い目で眺めるにとどめましょう！詳細は、明日以降に解説します。

データの準備

下の図は、コードの前段です。あとで登場する処理のための材料をここで準備しています。ようは、それぞれの変数を宣言しています。

Whileループとif文

そして、下の図にあるように、この後段部分がハイライトになります。目標とする値を見つけ出す処理が書いてあります。

探索する範囲が残り続ける限りループします。ただし、もちろん値が見つかればループは終了します。

そして核心は、次のコードです！中央値と探索する値の比較した結果に応じて3パターンに条件分岐させています。難しそうに見えて、丁寧に見ていけば、思ったより簡単であることに気づきます。

次回以降、詳細を深堀していきましょい！

ということで、今日は「二分探索」のソースの概要を眺めました。まだまだ続きますよ～。

ソースコードはこちらです。

#昇順で整列済みのデータをリストで用意
data = [0,1,3,5,6,8,9]
#探索する値を格納する変数
target = 8
#探索する値と同じ値を持つ番号を格納する変数
foundId = -1

#探索の開始番号を格納する変数
start = 0
#探索の終了番号を格納する変数
end = len(data) - 1

#探索範囲がある限りループ
while start <= end:
    #開始番号から終了番号までの番号のうち中央にある番号
    middle = (start + end) // 2
    #探索する値と、探索範囲の中央にある値が同じなら
    if target == data[middle]:
        #その値の番号を格納してループ終了
        foundId = middle
        break
    #探索する値の方が、中央にある値より大きいなら
    elif target > data[middle]:
        #探索の開始番号を、中央にあった番号の右隣りの番号に変更
        start = middle + 1
    #それ以外（探索する値の方が、中央にある値より小さい）なら
    else:
        #探索の終了番号を、中央にあった番号の左隣りの番号に変更
        end = middle - 1

#結果を出力
print("探索値と一致する値の番号は、",foundId)

では、ビーダゼーン！

※私のやる気アップとブログの品質向上につながりますので、記事が気に入られた方は、「ポチっ」と好きボタンを押してくださったり、フォローいただけますと幸いです🙇。