線形探索とは？

線形探索とは、配列やリストの先頭から順に要素を1つずつ調べ、目的の値と一致したところで終了する探索方法。逐次探索ともいう。データが整列されていなくても使える代わりに、平均比較回数は(n+1)/2回、最悪n回でO(n)となる点がFEで頻出。

せんけいたんさく

基本情報技術者試験の頻出用語／テクノロジ系

線形探索の意味

配列やリストの先頭から順に要素を1つずつ調べ、目的の値と一致したところで終了する探索方法。逐次探索ともいう。データが整列されていなくても使える代わりに、平均比較回数は(n+1)/2回、最悪n回でO(n)となる点がFEで頻出。

100件のデータから目的の値を探すとき、先頭にあれば1回、末尾にあれば100回の比較が必要で、存在する前提の平均は約50.5回。存在しない値を探した場合は必ず全件（100回）比較して初めて「無い」と分かる。

平均比較回数を n/2 と (n+1)/2 のどちらで答えるかが問われる。「見つかる場合の平均」は(n+1)/2、「見つからない場合」はn回（番兵ありならn+1回）である。二分探索と違い事前の整列が不要な点も対比される。

最終更新：2026-08-25／解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。