線形探索とは？

線形探索（逐次探索）とは、データを先頭から順に1つずつ調べて目的の値を探す、最も基本的な探索方法です。

仕組みが単純で、整列していないデータにもそのまま使えるのが利点。一方、目的の値が後ろにあるほど手数が増え、n個のデータでは最悪 n 回・平均 n/2 回の比較が必要で、計算量は O(n) です。

比較を少し速くする工夫が番兵法（ばんぺいほう）。データの末尾に探したい値そのものを番兵として置くと、「見つかったか」の判定だけでよくなり、「範囲を超えたか」の判定が不要になります。

基本情報技術者試験では、計算量 O(n)、番兵法、そして整列済みなら速い二分探索との比較が問われます。

🔗 関連：探索アルゴリズムの可視化（線形探索と二分探索を並べて比較）／ 二分探索 ／ 用語辞典トップ