IT用語入門：線形探索法【先頭から順に比較する単純な探索】

線形探索法とは

線形探索法は、配列やリストの先頭から要素を一つずつ取り出し、目的の値と一致するかを順に確かめる探索アルゴリズムです。見つかった時点で処理を止め、見つからなければ末尾まで確認します。リニアサーチ、逐次探索とも呼ばれます。

身近な例では、並び替えていない名簿から特定の名前を上から順に探す動作に近いです。データを事前にソートする必要がなく、追加の記憶領域もほとんど要りません。仕組みが簡単なので実装が短く、デバッグもしやすいのが特徴です。

性能は要素数に比例して増えます。要素がN個なら最悪でN回、平均ではおよそN/2回の比較が発生します。先頭付近に目的の値があると早く終わりますが、規模が大きくなるほど二分探索などの高度な手法に比べて遅くなりがちです。

小規模データや整列されていないデータを手早く調べたい場面で有効です。一方で大量データや繰り返し検索が必要な場合は、適切な前処理や別のアルゴリズムの採用を検討するとよいでしょう。