データの中で目的のものを探し当てる処理として、いくつかアルゴリズムがあります。アルゴリズムにはある種お約束的に使われる処理というのが多数存在しますが、その中でも代表的な探索アルゴリズムを紹介していきます。
線形探索法
まずは一番単純な探索アルゴリズムを考えてみます。例えば、
[5, 3, 9, 1, 2, 7, 6, 4, 8]
のような配列のデータから「2」を見つけ出すにはどうすればよいでしょうか。簡単なのは先頭から順に中身が2と一致するか比べていくことです。この方法を線形探索法と呼びます。アルゴリズムとしては以下のようになります。
- 配列の先頭から値を取り出す
- 取り出した値と目的の値を比較する
- 一致すれば終了。一致しなければ１に戻って次の値を取り出す
かなりシンプルです。実装してみます。
番兵を用いた方法
上の実装ではforとifで2回処理が発生するため、速度の面で効率的ではありません。そこで、終了判定を簡単にするため末尾に付加したデータ（番兵）を用意し、配列の中に目的のデータが必ず存在する状況を作ってしまいます。そうすることで、一致する値がなくても一番後ろの番兵で必ず停止してくれます。実装は以下のようになります。
線形探索法は順番に調べるだけなので分かりやすい方法ですが、値が見つかるまでしらみつぶしに調べるので、データが増えると処理に時間がかかります。ちなみに、データ数をnとしたときの平均探索回数は(n+1)/2回となります。（なぜかは調べてみてね！）