---
title: "線形探索とは？先頭から順番に探す基本アルゴリズム【基本情報技術者試験】"
description: "線形探索を先頭から順番にデータを確認する探索方法として整理し、二分探索との違い、計算量、科目Bの擬似言語問題での読み方をやさしく解説します。"
last_modified_at: "2026-06-23"
canonical_url: "https://stemtazoo.github.io/fe/linear-search/"
section: "fe"
---

## まず結論

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

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

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

## 直感的な説明

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

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

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

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

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

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

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

## 定義・仕組み

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

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

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

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

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

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

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

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

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

## 科目Aでどう出る？

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

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

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

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

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

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

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

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

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

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

## 科目Bでどう使う？

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

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

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

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

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

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

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

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

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

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

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

## よくある誤解・混同

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

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

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

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

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

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

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

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

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

## まとめ（試験直前用）

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