Pythonでアルゴリズム「二分探索」：リストの一番最後の番号って要素数と同じじゃないの？
では、Pythonでアルゴリズム「二分探索」の続きをやりますよ～。今回は、コードの詳細にジャンプインです！😉
前回記事でコードの概要は眺めてみましたから、今日は本題にささっと入りましょう！
探索の前提となる変数たちを仕込もう
では、コードの前段です。この内容を少し詳しく見ていきます。変数の宣言がたくさんありますね…。
リストでデータを準備
コードのしょっぱなでリスト型の変数を宣言しています。このデータの中から欲しい値を見つけ出します。数値自体は適当に見繕ってください😅。
ただし、ここで注目してほしいのは、数値が降順にならんでいるところです。二分探索は、数値が降順または昇順に規則的に並んでいることを利用して行う探索です。大小ばらばらに並べては、二分探索できませんよ。
「じゃあ、データの整列ってどうやるのよ～🤔」
う、来ましたね、その質問！実は、データの整列自体がアルゴリズムの
「一大テーマ」ですから、探索シリーズの後に、一つ一つ紹介したいと思います～。
ですので、いまは目視で自分で並べてくださいね🧡。
「見つける値」と「その場所を格納する変数」
つづいて、二つの整数型変数です。これは何でしたっけ？「線形探索」でも登場しました。
まず、targetは、「見つけたい値」ですね。今回は「8」としてみました。リストを眺めればすぐに分かりますね。前から6番目、すなわち、添字でいえば、「5」ということになります。
次に、foundIdですが、これは、探索の結果、targetと同じ値を見つけたら、その位置の番号（添字）を格納するための変数です。初期値で「-1」が入っています。つまり、この変数は、「見つけたい値」が見つからなかったときは、上書きされずに添字としてはあり得ない「-1」のままとなります。
以上を踏まえると、うまく探索できたなら、targetの値である「8」がfoundIdに格納される結果になるはずです。先に進む前に、これを抑えておきましょう🙂！
「探索の範囲」を決定する変数たち
お次は、こちらです。startとendと名付けた変数を見てみましょう！
「なんじゃこれ？見慣れませんね🤔」
確かに、「線形探索」には、登場しませんでした。実は、これらは、探索の範囲、具体的には、それぞれ「最初」と「最後」の添字を格納する変数です。絵にすると、次の図の通りです。
startは、探索範囲の「最初の数値の場所（添字）」を格納します。そして、「0」で初期化されています。すなわち、1回目の探索では、「リストの先頭から検索しようね」と言っているわけです。
これは理解しやすいですね～♪。
「-1」が重要でした。
一方、endは、探索範囲の「最後の数値の場所（添字）」を格納します。そして、「len(data) - 1」で初期化されています。すなわち、1回目の探索では、「リストの『len(data) - 1』まで検索しようね」と言っているわけです。
「この意味なんなのよ。『-1』とか入っているし！？😭」
突っ込まれなくても説明するつもりでしたよ～💦。まず、「len(data)」ですが、これは組み込み関数の「len」です。「リストの要素数」を戻してくれるのでした。引数は、data、すなわち、「探索対象のリスト」となっています。このリストの要素数は、「7」です。つまり、「len(data)」は、現在「7」という値と同じということになります。
「『-1』っているの！？添字「7」まで探索すればいいじゃん？🤔」
いや、「0～7まで」探索したら、要素数より１つ多くなっちゃいますよ～。添字が「0」から始まるから、ややこしいです。要素数n個のリストがあったとして、その一番最後の要素の番号（添字）は、「n-1」なんです。
ということで、「最後の数値の場所（添字）」は、「要素数から1つ減らしたもの」となります。もう、要素がn個で構成されているリストの一番最後の番号は、「n-1」なんだ～と覚えちゃいますか！
探索の範囲がどんどん狭くなる
では、もし探索を一回実行したら、startとendの変数がどうなるか、見てみましょうか！言葉で説明するより見た方が早いですな…。下のように絵にしました。
中央の値より、見つけたい値が大きいなら、もう左側は検索対象から外したいですね。なら、次の探索の開始位置（start）を上書きします。
一方、中央の値より、見つけたい値が小さいなら、もう右側は検索対象から外したいですね。なら、次の探索の終了位置（end）を上書きします。
（※中央の値と、見つけたい値が一致したら、探索完了です。念のため）
変数の使い方、見えてきましたね～。
よし、これでコードの前段の解説は、終了です。続いては、肝心の「探索アルゴリズム」に進もう！と思ったのですが、きりがいいのでいったんここで終了です。次回にしましょう！
では、ビーダゼーン！
※私のやる気アップとブログの品質向上につながりますので、記事が気に入られた方は、「ポチっ」と好きボタンを押してくださったり、フォローいただけますと幸いです🙇。