線形探索法とは？

線形探索法の意味

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

線形探索法の具体例

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

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

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

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

• 二分探索法

線形探索法が出た過去問

• 配列に格納されているデータを探索するときの、探索アルゴリズムに関する記述のうち、適切なものはどれか。

  正解：線形探索法で探索するのに必要な計算量は、探索対象となる配列の要素数に比例する。

  要点：線形探索の計算量は要素数に比例し、整列は不要

  線形探索は先頭から順に1つずつ調べるため、必要な比較回数は要素数に比例して増えます。2分探索は範囲を半分ずつ絞る方法で、あらかじめ整列されている必要があります。ただし、探す値が先頭にある場合などは線形探索のほうが少ない回数で見つかることもあります。

  出典：令和5年度 秋期 ITパスポート試験 問69（IPA）