線形探索とは？

詳細解説

線形探索（リニアサーチ）は、配列などのデータ構造において、先頭から末尾（または末尾から先頭）に向かって1要素ずつ順次比較しながら目的の値を探すアルゴリズムです。最も単純な探索方法であり、データが**ソート済みである必要がない**点が特徴です。計算量はO(n)で、n件のデータがあれば最悪n回の比較が必要です。具体的には、先頭要素から目的値と比較し、一致すれば終了、不一致であれば次の要素へ進むことを繰り返します。データが未整列でも使えることから、小規模データや一時的な検索に向いています。一方、大規模データでは探索回数が多くなるためパフォーマンスが低下します。FE試験の疑似言語問題では、線形探索の処理をトレースする問題や、「番兵（センチネル）法」（配列末尾に探索値を追加して終端チェックを省略する手法）を使った最適化コードの読解が出題されます。

FE試験での出題ポイント

• 1計算量O(n)：n件のデータで最悪n回比較が必要
• 2ソート不要（未整列データに使える）のが線形探索の強み
• 3番兵法：配列末尾に探索値を置いて範囲外チェックを省略する最適化
• 4二分探索との比較（前提条件・計算量の違い）

関連用語