前回、線形探索の考え方とプログラムを紹介しました。しかし線形探索は探したいデータの場所により時間がかかってしまう弱点があります。今回、高校「情報I」の教科書で紹介されているもう一つの探索手法を紹介します。二分探索です。
二分探索を簡単に説明すると、こうなります。
まず全てのデータを小さい順から並び替えします。次に、データを半分に分割します。検索したいデータが含まれている半分をさらに、半分に分割して、検索したいデータがどっちの半分にはいっているかを確認します。これを繰り返して最終的に検索したいデータの位置がわかります。
今回も、前回と同じ学習塾のデータを使います。
あなたはこどもICT塾の講師です。あなたのクラスには生徒10名います。先週英語の模擬試験を行いました。あなたは、それぞれの生徒の成績を表にまとめました。
では、あなたは、生徒IDが107番の生徒の成績を探したいです。二分探索のアルゴリズムはどのように動いているかを見てみましょう。
① 生徒ID番号はすでに小さい順になっていますので、そのまま使えます。
② 検索した生徒のIDを107に設定します。
③ 生徒IDの中央のデータを取り出します。今回は105になります。
④ 検索したいIDと比較します。107は105より大きいので後半の半分にあります。
⑤ 後半の半分の中央のデータを取り出します。今回は108になります。
⑥ 検索したいIDと比較します。107は108より小さいので前半の半分にあります。
⑦ 前半の半分の中央のデータを取り出します。今回は107になります。
⑧ 検索したいIDと比較します。107は107と同じので、検索対象を見つけました。
探索を中断します。
⑨ その行の左から3番目のデータが英語の成績となります。
⑩ 見つけた英語成績を表示します。
ステップが少し多いですが、③から⑧までは繰り返して実行されます。
では、上記の１０のステップを踏まえ、実際のプログラムを書いてみましょう。
JavaScriptを使います。
実行した結果は前回の線形探索と同じです。
しかし、処理の回数は線形探索よりはるかに少なくなります。このようなアルゴリズムはたくさん存在します。高校生にはすべてを学んでもらうのではなく、基本のアルゴリズムを学んで、プログラミングの考え方を身につけてもらいます。その考え方が高校生たちの今後の学びや仕事には役に立ちます。
プログラミングを教えるなら、ぜひ一度高校の「情報」教科書を手に入れて、勉強してみてください。プログラミング授業で何を教えればいいか、見えてくるはずだと思います。