前回、①に戻り、補助記憶装置(HDD・SSD)を整理しました。今回は、科目Bのアルゴリズム本編として、「探索アルゴリズム」を整理します。
探索アルゴリズムとは
探索アルゴリズムとは、配列などのデータの中から、目的の値を見つけ出すための手順のことです。基本情報技術者試験では、代表的な方法として「線形探索」と「二分探索」の２つが出題されます。
線形探索とは
線形探索は、配列の先頭から順番に、１つずつ値を確認していく方法です。目的の値が見つかるまで、あるいは配列の最後まで、順番に比較を続けます。
シンプルで分かりやすい方法ですが、配列の中に目的の値がなかった場合や、後ろのほうにある場合、確認する回数が多くなってしまうという弱点があります。
二分探索とは
二分探索は、あらかじめ並び替えられた(昇順や降順に整列された)配列に対して使える方法です。配列の真ん中の値と目的の値を比較し、目的の値がそれより大きいか小さいかによって、探す範囲を半分に絞り込んでいきます。
例えば、１から100までの数の中から目的の値を探す場合、まず中央の値(50前後)と比較し、目的の値のほうが大きければ後半、小さければ前半、というように、探す範囲を毎回半分にしていきます。この「範囲を半分に絞り込む」という操作を繰り返すことで、線形探索に比べて、少ない比較回数で目的の値にたどり着けます。
２つの探索方法の使い分け
線形探索と二分探索には、それぞれ次のような特徴があります。
- 線形探索:配列が整列されていなくても使える。ただし、配列が大きくなるほど時間がかかる
- 二分探索:配列があらかじめ整列されている必要がある。ただし、線形探索よりも少ない回数で探索できる
科目Aで学んだ「二分探索は、探すたびに範囲が半分になる」という性質は、探索にかかる回数の見積もりにもつながる、大事なポイントです。
トレースするときの注意点
二分探索をトレースするときは、「中央の値をどう計算しているか」を最初に確認するようにしています。配列の要素数が偶数か奇数かによって、中央の位置の計算方法が変わることがあるため、問題文の定義を丁寧に確認することが欠かせません。
学習してみた感想
線形探索は直感的に理解できましたが、二分探索は、最初「範囲を半分にする」という操作を、頭の中だけで追おうとすると混乱しました。実際に、探す範囲の両端の添字をノートに書き出しながらトレースする練習をしたことで、少しずつ感覚がつかめてきました。
次回は、ソートアルゴリズム(バブルソート・選択ソート)を整理します。
