線形探索とは？

線形探索の意味

配列やリストの先頭から順に要素を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回）である。二分探索と違い事前の整列が不要な点も対比される。

線形探索と関連する用語

• 2分探索
• 番兵

線形探索が出た過去問

• 探索表の構成法を例とともにa〜cに示す。最も適した探索手法の組合せはどれか。ここで，探索表のコードの空欄は表の空きを示す。

  正解：ア：a=2分探索，b=線形探索，c=ハッシュ表探索

  要点：整列順は2分探索、頻度順は線形探索、計算位置はハッシュ表探索。

  探索表の格納方法によって最適な探索法は変わる。コード順に整列して格納されている表は、中央と比較して範囲を半分に絞れるので2分探索が有効である。使用頻度の高い順に並べた表は先頭から順に見ると早く見つかるため線形探索が適し、コードから計算した位置に飛び飛びに格納した表はハッシュ表探索が適する。

  出典：平成30年度 秋期 応用情報技術者試験 午前 問8（IPA）

• 異なるn個のデータが昇順に整列された表がある。この表をm個のデータごとのブロックに分割し、各ブロックの最後尾のデータだけを線形探索することによって、目的のデータ…

  正解：m/2 + n/2m

  要点：平均比較回数は最悪回数の半分、2段階なら和で求める

  表はn÷m個のブロックに分かれる。まず各ブロック末尾のデータを線形探索するので、目的のブロックが見つかるまでの平均比較回数はブロック数の半分、すなわちn/2m回である。次に見つけたブロック内でm個のデータを線形探索するので平均m/2回かかる。両者を足したm/2＋n/2mが答えとなる。

  出典：平成30年度 春期 応用情報技術者試験 午前 問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 となる。

  出典：令和5年度 春期 応用情報技術者試験 午前 問6（IPA）

• 異なるn個のデータが昇順に整列された表がある。この表をm個のデータごとのブロックに分割し、各ブロックの最後尾のデータだけを線形探索することによって、目的のデータ…

  正解：m/2＋n/2m

  要点：線形探索の平均比較回数は要素数の半分になる

  表はn/m個のブロックに分かれる。まず各ブロック末尾の値を線形探索してブロックを特定するので、その平均比較回数はブロック数の半分でn/(2m)回になる。次に見つけたブロック内をm個から線形探索するのでm/2回。合計はm/2＋n/(2m)回となる。

  出典：令和7年度 秋期 応用情報技術者試験 午前 問6（IPA）