線形探索とは？せんけいたんさく
線形探索とは、配列やリストの先頭から順に要素を調べ、目的の値と一致した時点で終了する探索法。逐次探索ともいう。整列されていないデータにも使える代わりに計算量はO(n)で、比較回数はデータ量に比例して増える。末尾に番兵を置くと終端判定が不要になり、比較の分岐が1つ減る。
最終更新：2026-10-06
この語が出る過去問を解く →背景
探索を速くする手法はどれも前提を必要とする。2分探索は整列済みであること、ハッシュ表探索は索引構造を作っておくことが条件で、その前提を用意する側にも整列や表構築の費用がかかる。データが少ない場合や一度しか探さない場合は、前提を作らずに済む線形探索のほうが総費用で勝つ。計算量の丸暗記ではなく、前処理まで含めて選べるかが応用情報で問われる観点である。
具体例
1,000件から探すとき、線形探索の平均比較回数は約500回、2分探索は約10回で済む。ただし未整列なら整列にO(n log n)がかかるため、探索が1回きりなら線形探索のほうが総費用は小さい。Pythonのリストに対する in 演算子や list.index() は、この線形探索そのものである。
試験での引っ掛け
平均比較回数の場合分けが狙われる。データ中に必ず存在する前提での平均は(n+1)/2、存在しないと判明するまでにはn回（番兵ありならn+1回）で、n/2と答えさせる選択肢が並ぶ。2分探索と違って事前の整列が不要な点、要素を追加するたびに整列し直さなくてよい点も対比の的になる。
関連用語
出た過去問
出典：平成30年度 秋期 応用情報技術者試験 午前 問8（IPA）
探索表の構成法を例とともにa〜cに示す。最も適した探索手法の組合せはどれか。ここで，探索表のコードの空欄は表の空きを示す。
正解：ア：a=2分探索，b=線形探索，c=ハッシュ表探索
要点：整列順は2分探索、頻度順は線形探索、計算位置はハッシュ表探索。
探索表の格納方法によって最適な探索法は変わる。コード順に整列して格納されている表は、中央と比較して範囲を半分に絞れるので2分探索が有効である。使用頻度の高い順に並べた表は先頭から順に見ると早く見つかるため線形探索が適し、コードから計算した位置に飛び飛びに格納した表はハッシュ表探索が適する。
出典：平成30年度 春期 応用情報技術者試験 午前 問6（IPA）
異なるn個のデータが昇順に整列された表がある。この表をm個のデータごとのブロックに分割し、各ブロックの最後尾のデータだけを線形探索することによって、目的のデータ…
正解：m/2 + n/2m
要点：平均比較回数は最悪回数の半分、2段階なら和で求める
表はn÷m個のブロックに分かれる。まず各ブロック末尾のデータを線形探索するので、目的のブロックが見つかるまでの平均比較回数はブロック数の半分、すなわちn/2m回である。次に見つけたブロック内でm個のデータを線形探索するので平均m/2回かかる。両者を足したm/2＋n/2mが答えとなる。
出典：令和5年度 春期 応用情報技術者試験 午前 問6（IPA）
従業員番号と氏名の対がn件格納されている表に線形探索法を用いて、与えられた従業員番号から氏名を検索する。この処理における平均比較回数を求める式はどれか。ここで、…
正解：(n+1)(1-a)/2 + na
要点：線形探索の平均比較回数は、成功時(n+1)/2・失敗時n
表に存在する場合（確率1-a）は、目的の要素が先頭からn番目までのどこかに等確率であるので平均比較回数は(n+1)/2になる。存在しない場合（確率a）は末尾まで調べ切るのでn回である。両者を確率で重み付けして足すと(n+1)(1-a)/2 + na となる。
出典：令和7年度 秋期 応用情報技術者試験 午前 問6（IPA）
異なるn個のデータが昇順に整列された表がある。この表をm個のデータごとのブロックに分割し、各ブロックの最後尾のデータだけを線形探索することによって、目的のデータ…
正解：m/2＋n/2m
要点：線形探索の平均比較回数は要素数の半分になる
表はn/m個のブロックに分かれる。まず各ブロック末尾の値を線形探索してブロックを特定するので、その平均比較回数はブロック数の半分でn/(2m)回になる。次に見つけたブロック内をm個から線形探索するのでm/2回。合計はm/2＋n/(2m)回となる。
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。