テクノロジ系出題頻度 3/3
線形探索
せんけいたんさく
定義
配列やリストを先頭から順に調べる探索アルゴリズム。計算量はO(n)。
詳細解説
リニアサーチ。データを先頭から順に比較し、目的値が見つかるか末尾まで到達したら終了する。データが整列されている必要がなく実装が単純。最良ケースO(1)、平均・最悪O(n)。短いリストや稀な検索、ハッシュキーが利用できないケースに適する。番兵法（センチネル）を使うと比較回数を減らせる。整列済みなら二分探索（O(log n)）が圧倒的に高速だが、整列コストとのトレードオフがある。
「線形探索」が出る問題
関連用語
よくある質問
Q. 線形探索とは何ですか？
A. 配列やリストを先頭から順に調べる探索アルゴリズム。計算量はO(n)。
Q. 応用情報技術者試験での位置づけは？
A. テクノロジ系の重要用語です。出題頻度は 3/3 （★3）。 頻出のため確実に押さえておきましょう。