対象試験と出題頻度
線形探索法（リニアサーチ）は、基本情報技術者・応用情報技術者で出題されるテーマです。
科目Aでは「平均比較回数を求める式」を選ばせる計算問題が定番で、科目Bでは擬似言語による探索処理のトレース問題として登場します。
二分探索法やハッシュ表探索法との使い分けを正確に理解しているかが問われます。
詳細をクリックして確認
基本情報技術者
応用情報技術者
★★★☆☆
ランクB（標準）覚えておくと有利
用語の定義
情報処理試験を勉強していると、「探索アルゴリズムっていくつもあるけど、線形探索って結局何が違うの？」と迷いがちです。
線形探索法（Linear Search / Sequential Search）とは、一言で言うと
「配列やリストの先頭から末尾まで、データを1つずつ順番に比較して目的の値を探し出すアルゴリズム」
のことです。
イメージとしては、「本棚の左端から1冊ずつタイトルを確認して、目当ての本を探す」こと。
五十音順に並んでいなくても問題なく、とにかく端から順番に見ていく。これが線形探索法の考え方です。
📊 線形探索法の基本情報
| 項目 | 内容 |
|---|---|
| 英語名 | Linear Search / Sequential Search |
| 別名 | 逐次探索法（ちくじたんさくほう） |
| 計算量（平均） | O(n) ※データ件数nに比例 |
| 前提条件 | データの整列（ソート）は不要 |
解説
探索アルゴリズムにはいくつかの種類がありますが、線形探索法はその中で最もシンプルな手法です。「データが整列されていなくても使える」という点が大きな特徴で、事前準備なしにすぐ適用できます。
探索の流れ
配列の先頭（インデックス0）から順に、目的の値と一致するかを1要素ずつ比較します。一致した時点で探索は終了し、その位置（インデックス）を返します。末尾まで比較しても見つからなければ「該当なし」と判定します。
🔍 線形探索の動作イメージ（目的の値：7）
| index | 0 | 1 | 2 | 3 | 4 |
| 配列 | 3 | 5 | 1 | 7 | 9 |
| 比較 | 1回目 ✗ | 2回目 ✗ | 3回目 ✗ | 4回目 ✓ | ― |
先頭から順に比較し、index 3 で一致 → 探索終了（比較4回）
平均比較回数の公式
n件のデータに対して線形探索を行う場合、目的のデータが必ず存在するなら、最小比較回数は1回（先頭にある場合）、最大比較回数はn回（末尾にある場合）です。よって平均比較回数は (n + 1) / 2 回になります。
目的のデータが存在しない確率を a とすると、存在しない場合は必ずn回の比較が必要になるため、全体の平均比較回数は次の式で表されます。
📐 平均比較回数の公式
(n + 1)(1 − a) / 2 + na
n：データ件数 a：目的データが存在しない確率
番兵法による改良
線形探索法では、ループのたびに「目的の値と一致するか」と「配列の末尾を超えていないか」の2つの条件を判定します。
番兵法は、配列の末尾に目的の値のコピー（番兵）をあらかじめ追加しておくことで、末尾チェックを省略する改良手法です。必ずどこかで一致するため、ループ終了後に見つかった位置が番兵の位置かどうかで存在の有無を判定します。
▶ 番兵法の擬似コード（クリックで展開）
// 配列 data[0..n-1] から値 key を線形探索（番兵法）
function sentinelSearch(data[], n, key)
data[n] ← key // 末尾に番兵を配置
i ← 0
while data[i] ≠ key
i ← i + 1
endwhile
if i < n
return i // 見つかった位置を返す
else
return -1 // 見つからなかった
endif
endループ内の条件が1つだけになるため、比較回数が削減されます。
二分探索法・ハッシュ表探索法との比較
線形探索法を正しく位置づけるには、他の探索手法との違いを整理するのが近道です。
| 探索手法 | 平均計算量 | 前提条件 | 特徴 |
|---|---|---|---|
| 線形探索法 | O(n) | 整列不要 | 最もシンプル。少量データ向き |
| 二分探索法 | O(log n) | 整列済みであること | 中央値と比較し探索範囲を半分に絞る |
| ハッシュ表探索法 | O(1) | ハッシュ関数による格納 | 最速だがシノニム（衝突）の処理が必要 |
ここだけは確実に押さえてください。線形探索法は「整列不要で使えるが計算量はO(n)」、二分探索法は「整列済みが前提だがO(log n)で高速」という対比が最重要です。
では、この用語が試験でどのように出題されるか見ていきましょう。
💡 線形探索法の核心を3行で
・先頭から末尾へ1つずつ比較し、目的のデータを見つける最も基本的な探索アルゴリズム
・平均比較回数は (n + 1) / 2 回、存在しない確率 a を含めると (n + 1)(1 − a) / 2 + na
・データの整列が不要な点が二分探索法との最大の違い
試験ではこう出る！
線形探索法は、基本情報技術者・応用情報技術者の科目Aで繰り返し出題されています。科目Bでも擬似言語を使った探索処理のトレース問題として登場する定番テーマです。
📊 過去問での出題実績
| 試験回 | 出題内容 | 問われたポイント |
|---|---|---|
| AP R5春 午前 問6 |
n件のデータに対して線形探索法で検索するときの平均比較回数の式を選ぶ問題。存在しない確率 a を含む。 | ・(n+1)(1−a)/2 + na を導出できるか ・H26春AP問6の再出題 |
| AP H30春 午前 問6 |
ブロック分割＋線形探索を2回組み合わせた場合の平均比較回数を求める問題。 | ・n/2m + m/2 を導出できるか ・FE R4免除問9と同一問題 |
| FE R4免除 問9 |
AP H30春問6の流用。ブロック分割＋逐次探索の平均比較回数。 | ・AP・FE間で同一問題が出回る典型例 |
| FE H16春 午前 問15 |
流れ図を用いた線形探索の動作結果を問う問題。 | ・流れ図を正確にトレースできるか |
📝 IPA試験での出題パターン
パターン1：「平均比較回数の式を選べ」（科目A）
AP・FEで最も多い出題形式。存在しない確率 a を含む公式を導出させる問題と、ブロック分割を組み合わせた応用問題の2パターンがある。「最小1回・最大n回 → 平均 (n+1)/2」を起点に立式できれば正解にたどり着ける。
パターン2：「擬似言語で探索処理をトレースせよ」（科目B）
科目Bでは、配列に対する逐次探索のプログラムを擬似言語で示し、変数の値や戻り値を問う問題が出る。番兵を配置してループ条件が1つだけになるコードも頻出。ループの終了条件と戻り値の判定を正確に追えるかがカギ。
試験ではここまででOKです。計算量のオーダー記法（O記法）の詳細や、より高度な探索木の知識は深追い不要です。
【確認テスト】理解度チェック
ここまでの内容を理解できたか、簡単なクイズで確認してみましょう。
Q. n件のデータが格納された配列に対する探索手法の説明として、線形探索法に該当するものはどれでしょうか？
- A. データをあらかじめ昇順に整列しておき、中央の要素と目的の値を比較して探索範囲を半分に絞る操作を繰り返す。平均計算量は O(log n) である。
- B. データの整列を必要とせず、先頭から末尾へ1つずつ順に比較して目的の値を探す。目的データが存在する場合の平均比較回数は (n + 1) / 2 回である。
- C. データの格納位置をハッシュ関数で算出し、算出されたアドレスに直接アクセスして探す。シノニムが発生しなければ平均計算量は O(1) である。
正解と解説を見る
正解：B
解説：
線形探索法は、整列されていない配列に対しても適用でき、先頭から順に比較していく手法です。目的データが存在する場合、最小1回・最大n回の比較となるため、平均は (n + 1) / 2 回になります。
選択肢Aは二分探索法の説明です。中央値との比較で探索範囲を半減させるため高速ですが、データが整列済みであることが前提条件です。選択肢Cはハッシュ表探索法の説明です。ハッシュ関数で格納位置を直接計算するため最も高速ですが、衝突（シノニム）が発生すると追加の処理が必要になります。
よくある質問（FAQ）
Q. 線形探索法はデータ件数が多いと遅いのに、なぜ実務でも使われるのですか？
データ件数が数十件程度であれば、二分探索法やハッシュ表探索法との速度差は体感できないレベルです。整列やハッシュテーブルの構築といった事前処理が不要なため、少量データの検索や、1回しか探索しない場面ではコードの単純さがメリットになります。実装ミスのリスクも低いため、プロトタイプ開発や一時的なスクリプト処理で選ばれることがあります。
Q. 「逐次探索法」と「線形探索法」は別物ですか？
同じものです。IPAの試験問題やシラバスでは「線形探索法」と表記されることが多いですが、参考書によっては「逐次探索法」「シーケンシャルサーチ」と書かれている場合があります。どの名前で出題されても同一の手法を指しているので、「先頭から順に比較する」という動作を思い出せば対応できます。
Q. 番兵法を使うと、なぜ高速化されるのですか？
通常の線形探索では、ループのたびに「値が一致したか」と「配列の末尾を超えていないか」の2つの条件判定が必要です。番兵法では末尾に目的の値を置くため、必ずどこかで一致することが保証されます。結果としてループ内の条件判定が1つだけになり、比較回数がおよそ半減します。データ件数が多いほどこの差が効いてきます。
Q. 線形探索法の計算量 O(n) とはどういう意味ですか？
O(n)は「データ件数nに比例して処理時間が増える」という意味のオーダー記法（ビッグオー記法）です。データが100件なら最大100回、1,000件なら最大1,000回の比較が必要になります。二分探索法のO(log n)と比べると、nが大きくなるほど差が広がります。たとえばn=1,000,000のとき、線形探索は最大100万回の比較が必要ですが、二分探索は約20回で済みます。
