テクノロジ系 / アルゴリズムとプログラミング

線形探索（逐次探索）

先頭から順に1つずつ比較して目的のデータを探す、最も基本的な探索法です。

別名・関連表記：線形探索、逐次探索、リニアサーチ

もう少し詳しく

線形探索は、データを先頭から末尾へ順番に調べ、一致するものを見つける方法です。データが整列していなくても使え実装が簡単ですが、n個のデータでは平均比較回数が約n／2、最悪でn回となり、計算量はO(n)です。番兵（探したい値を末尾に置く工夫）を使うと、終了判定の比較を1つ減らして高速化できます。

黒猫の闇の刻印

平均比較回数（n＋1）／2、最悪n回、計算量O(n)が問われます。整列済みデータで使える二分探索O(log n)との違いが頻出です。「端から順番に総当たり」。整列不要だが遅い。

例：100件から線形探索すると平均約50回の比較で見つかります（二分探索なら約7回）。

テクノロジ系 / 基礎理論 / アルゴリズムとプログラミング

小分類：アルゴリズム

関連トピック：整列・併合・探索のアルゴリズム

IPA FEシラバス Ver.9.2 の用語例をもとに、試験対策向けに独自解説しています。