日常のアルゴリズムを体感するシリーズ。今回は、ものを順番に探すアルゴリズムであるリニアサーチについて解説します。

リニアサーチとは

サーチ（探索）アルゴリズムの中でも一番簡単なアルゴリズムです。別名「線形検索」とも呼ばれ、グループの中から指定した値を先頭から順番に探します。

例えば、1から5まで並んだ列（並びは順番でも、ランダムでもOK）の中から「4」という値が見つかったら「見つかったことを伝える」ことをゴールとして例を見てみましょう。

最初に検索するのは1という値ですが、これは4ではないため該当しません。この場合は次の値の比較に進みます。その後も2と3はもちろん4ではないので次に進みます。

次の4は目的としていた値のため、ここで「見つかったとを伝えて」終了となります。

「見つかったことを伝える」というのは少々半端な表現ですが、実際にこのサーチアルゴリズムをプログラミングする場合だと「見つかった値」や「何番目に探していた値があったか」など、目的とする結果が異なる場合がありますので、今回は抽象的な表現としました。

なお、一般的なリニアサーチでは、グループの中に同じ値が含まれている場合は最初に見つかったものが優先されます。つまり、先ほどと同様に「4」という値を検索する場合、検索対象となるグループが「1、4、5、4、3」という値であった場合、1の次に登場する4が見つかった時点で「見つかった」という判断となります。その後の５、4、3は検索されずに終了します。

リニアサーチを体験する「宝探しゲーム」

リニアサーチを身体を使って覚えるために「宝探しゲーム」で楽しんでみましょう。これは、買い物競争のような要領で、指定した値（お宝）を持っている人を探します。

買い物競争では当てずっぽうで探したり、声掛けをして探したりしますが、今回あリニアサーチを体験することが目的のため、お宝を持っている人は順番に並び先頭の人から順番に探すものとします。順番の並びは出席番号順でも背の順でも構いません。探す対象は5名から10名程度の人数が良いでしょう。

また、探すお宝もなんでも良いです。数値でも、身の回りのものでもOKです。探す人が迷わないように、最低限、ジャンルだけは統一します。

あとは、先頭の人から順番に「◯◯さんは××を持っていますか？」という質問をしながら、目的のお宝を探していきます。もし見つかった場合は「見つかった！」と大きな声で伝えましょう。仮に見つからなかった場合は「見つからなかった！」と伝えましょう。

探した時間を競うでも良いですし、何回質問をしたかの数で勝負してみるのも盛り上がるかもしれません。

リニアサーチはサーチアルゴリズムの基本

今回の解説を読んでいただくと、おそらく日常的に探しものをするときの動作に似ているということにお気づきになると思います。リニアサーチはまさしく日常的にあなたが行っている動作をアルゴリズムとして表現しているだけであり、難しいものではありません。

サーチアルゴリズムの基本として、ぜひ扱ってみてください。