最終更新日：2026年6月23日

fe fe-technology algorithm data-structure

まず結論

線形探索とは、データを先頭から順番に見て、目的の値を探す方法です。

基本情報技術者試験では、探索アルゴリズムの基本として出題されます。

ポイントは、整列されていないデータにも使えるが、データ数が多いと時間がかかりやすいことです。

直感的な説明

線形探索は、名簿を上から順番に見て、目的の名前を探すイメージです。

例えば、次のような名簿があるとします。

1番目：佐藤
2番目：田中
3番目：山本
4番目：鈴木

ここから「山本」を探すなら、上から順に確認します。

佐藤ではない
田中ではない
山本だった

このように、一つずつ順番に確認するのが線形探索です。

英語では linear search と呼ばれます。
linear は「直線的な」という意味なので、前からまっすぐ順番に探すイメージです。

定義・仕組み

線形探索では、配列などに入っているデータを、先頭から順に確認します。

基本的な流れは次のとおりです。

1. 先頭の要素を見る
2. 探している値と一致するか確認する
3. 一致すれば探索を終了する
4. 一致しなければ次の要素を見る
5. 最後まで見つからなければ「見つからない」と判断する

例えば、配列 a に次の値が入っているとします。

a[0] = 8
a[1] = 3
a[2] = 6
a[3] = 2

ここから 6 を探す場合、次の順で確認します。

a[0] = 8 → 違う
a[1] = 3 → 違う
a[2] = 6 → 見つかった

線形探索は、配列が小さい場合や、データが整列されていない場合でも使いやすい方法です。

線形探索は、基本情報技術者試験の「アルゴリズムとプログラミング」や、配列などの「データ構造」と関係が深いテーマです。公式の出題範囲は、IPA：基本情報技術者試験 から確認できるシラバスで確認できます。

科目Aでどう出る？

科目Aでは、線形探索は探索アルゴリズムの特徴として問われやすいです。

特に見るべきポイントは次の3つです。

  • 先頭から順番に探す
  • データが整列されていなくても使える
  • 最悪の場合、最後まで調べる必要がある

例えば、次のような説明は線形探索の説明として自然です。

配列の要素を先頭から順に調べ、目的の値と一致するか確認する。

一方で、次のような説明は二分探索の説明です。

探索範囲を半分ずつ狭めながら目的の値を探す。

線形探索は、考え方は単純です。
その代わり、データ数が多いと確認回数が増えやすくなります。

計算量で表すと、線形探索の平均・最悪の計算量はおおむね O(n) と考えます。

ただし、FEでは式だけを覚えるより、データ数が増えると確認回数もほぼ比例して増えると理解するのが大切です。

科目Bでどう使う？

科目Bでは、線形探索は擬似言語のトレース問題でよく使う考え方です。

例えば、次のような処理が出たら、線形探索の流れとして読めます。

i を 0 から 配列の末尾 まで増やす
    もし a[i] が 探す値 と等しければ
        見つかった位置を記録する

読むときは、次の順で確認すると整理しやすいです。

  1. 探している値は何か
  2. どの配列を見ているか
  3. 添字がどの順番で変わるか
  4. 一致したときに処理を終了するか
  5. 見つからなかったときに何を返すか

特に注意したいのは、見つかったあとも処理が続くかどうかです。

例えば、最初に見つかった位置を返す処理なら、見つかった時点で探索を終了します。

一方で、同じ値が何個あるかを数える処理なら、見つかっても最後まで確認する必要があります。

この違いを見落とすと、科目Bで答えがずれやすくなります。

また、配列の添字が 0 から始まるか、1 から始まるかにも注意します。

FEの擬似言語では、問題文で指定された添字の扱いに従うことが大切です。

よくある誤解・混同

線形探索で一番混同しやすいのは、二分探索です。

探索方法 探し方 整列の必要 イメージ
線形探索 先頭から順番に探す 不要 名簿を上から見る
二分探索 範囲を半分ずつ狭める 必要 辞書を開いて探す

線形探索は、データが整列されていなくても使えます。

一方、二分探索は、基本的にデータが整列されていることが前提です。

ここが大事な切り分けです。

  • 整列されていないデータをそのまま探す → 線形探索
  • 整列済みのデータを効率よく探す → 二分探索

また、「線形探索はいつも遅い」と覚えるのも少し危険です。

データ数が少ない場合や、目的の値が早い位置にある場合は、線形探索でもすぐに見つかります。

試験では、単に速い・遅いではなく、前提条件と探し方で判断します。

まとめ（試験直前用）

  • 線形探索は、先頭から順番に目的の値を探す方法
  • 整列されていないデータにも使える
  • 最悪の場合、最後の要素まで確認する
  • データ数が増えると確認回数も増えやすい
  • 二分探索との違いは「整列が必要か」と「探し方」

© 2024-2026 stemtazoo. All rights reserved.