線形探索法とは？

線形探索法の意味

データを先頭から順番に1つずつ調べて目的の値を探す方法。データが整列（ソート）されていなくても使えるが、データ件数が多いほど時間がかかる。

線形探索法の具体例

名簿が五十音順に並んでいなくても、先頭から1件ずつ「探している名前と一致するか」を確認していけば必ず見つかる。ただし1000件あれば最大1000回の比較が必要になりうる。

線形探索法は試験でどう引っ掛けられる？

平均比較回数は「データ件数÷2」程度になる（毎回全件調べるわけではない）。

線形探索法と関連する用語

• 線形探索法・二分探索法・ハッシュ探索法

線形探索法が出た過去問

• 従業員番号と氏名の対が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）