探索アルゴリズム（線形探索と二分探索）

背景・歴史

コンピュータが扱うデータ量が増えるにつれ、「この配列の中に目的の値はあるか、あるとしたらどこにあるか」を効率よく見つけ出す方法が重要な研究課題になりました。最も単純な方法は、データを端から順番に1つずつ確認していく方法ですが、データ量が膨大になると非常に時間がかかります。そこで、あらかじめデータを並べ替えておくことを前提に、探索する範囲を半分ずつに絞り込んでいく、より効率的な探索方法が考案されました。

なぜこの考え方が使われるようになったのか

探索の速さは、データの量が多くなるほど重要になります。何十万件ものデータの中から1件を探すとき、端から順番に調べる方法では非常に時間がかかりますが、範囲を半分ずつ絞り込む方法を使えば、はるかに少ない回数の比較で目的のデータにたどり着くことができます。目的やデータの状態に応じて適切な探索アルゴリズムを選ぶことは、プログラムの実行速度を大きく左右します。

もう少し詳しく見てみる

• 線形探索：データの先頭から順番に1つずつ、目的の値かどうかを確認していく方法。データが並べ替えられている必要はありませんが、データ数が多いほど時間がかかります。
• 二分探索：あらかじめ並べ替えられたデータに対して、中央の値と目的の値を比較し、範囲を半分に絞り込むことを繰り返す方法。線形探索よりもずっと少ない比較回数で目的のデータを見つけられますが、事前にデータが並べ替えられている必要があります。

例えば、辞書で言葉を探すとき、最初のページから順番にめくるのではなく、大まかに開いたページと目的の言葉を見比べて、探す範囲を半分に絞り込んでいく探し方は、二分探索の考え方に近いものです。データ数が多いほど、この効率の違いは大きくなります。

関連して知っておきたいこと

探索アルゴリズムの効率の違いは、計算量という指標を使って比較することができます。線形探索と二分探索では、データ数が増えたときに必要な処理時間の増え方が大きく異なり、この違いを理解することがアルゴリズムの設計において重要です。