Pythonでアルゴリズム「二分探索」：if文による条件分岐がキモであることが分かりました
Pythonでアルゴリズム「二分探索」の続きです。前回は、「二分探索」とは何か、その最初のステップをご紹介しました。今回は、Pythonでのコードを考えてみることにしましょう。
絵で見る「二分探索」
しかし、その前に、前回記事の補足です。二分探索の仕組みをさらにビジュアル化しました。これで、もっと分かりやすくなるかしらん🤔
最初のループで、「真ん中の値」＜「目標の値」であることが分かりました。「真ん中の値」より小さい値は、探索対象から外れます。
第2回目のループでは、「目標の値」＜「真ん中の値」であることが分かりました。「真ん中の値」より大きい値は、探索対象から外れます。
第3回目のループで、「真ん中の値」＜「目標の値」であることが分かりました。「真ん中の値」より小さい値は、探索対象から外れます。
第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)では、ビーダゼーン！
※私のやる気アップとブログの品質向上につながりますので、記事が気に入られた方は、「ポチっ」と好きボタンを押してくださったり、フォローいただけますと幸いです🙇。