線形探索とは（全体像）
線形探索（逐次探索）とは、データを先頭から順に1つずつ調べていき、目的のものを見つける探し方のことだ。
本棚から1冊を探すとき、端から順に1冊ずつ見ていくイメージ。とても素直なやり方だ。
ここで一番のポイント。線形探索は、並べ替え（ソート）が要らない。データがバラバラに並んでいても、先頭から見ていけば探せる。「線形探索にはソートが必要」と思い込むと誤りになる（ソートが必要なのは、別の探し方である2分探索のほう）。
詳しく：ソート不要と、速さの目安
ここが心臓部。線形探索の特徴を押さえよう。
線形探索のポイント
| 項目 | やさしい意味 |
|---|---|
| 探し方 | 先頭から順に1つずつ調べる |
| ソート | 不要（並んでいなくても探せる） |
| 実装 | かんたん |
| 速さ | データが多いと時間がかかる（最悪は全部調べる） |
線形探索のよいところは、ソートが要らず、作るのが簡単なこと。少ないデータなら、これで十分だ。
ただし、データが多いと、時間がかかる。目的のものが末尾にあったり、そもそも無かったりすると、最後まで全部調べることになる（最悪のとき、件数ぶんの比較が必要＝O(n)）。だから、「線形探索はいつも高速」と思い込むと誤りだ。データが多く、しかも並べ替えてあるなら、2分探索のほうが速いこともある。
わかりやすく言い換えると
身近なたとえで整理しよう。
線形探索は、「本棚の端から、1冊ずつ順に見ていく探し方」のイメージ。並んでいなくても探せるのが強みだ。
「ソート不要」というのは、データが並べ替えられていなくても、そのまま探せること。要するに、準備がいらない。
「データが多いと遅い」というのは、冊数が増えるほど、見る回数も増えること。つまり、件数に比例して時間がかかる。
試験のツボ
🔴 一番出る：線形探索の正体
①データを先頭から順に1つずつ調べて探す
②素直で、実装が簡単な探し方
🔴 次に出る：ソート不要
①並べ替え（ソート）が要らない
②データがバラバラでも、そのまま探せる
🟡 押さえると安定：速さの目安
①データが多いと時間がかかる（最悪は全部調べる＝O(n)）
②並べ替え済みなら、2分探索のほうが速いこともある
よくある間違い
①「線形探索は、つねに高速に探せる」→ ✗ データが多いと、最悪は全部調べる（O(n)）。並べ替え済みなら2分探索が速いことも。
②「線形探索には、あらかじめ並べ替え（ソート）が必要だ」→ ✗ 線形探索はソート不要。ソートが必要なのは2分探索のほう。
③「線形探索は、データの真ん中から調べていく方法だ」→ ✗ 真ん中から調べるのは2分探索。線形探索は、先頭から順に調べる。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（線形探索の正体）
線形探索に関する次の記述のうち、最も適切なものはどれか。
- 社員の出退勤を記録して、毎月の給与を計算するためのしくみである
- 取引先へ毎月の請求書を郵送する、決まった事務作業のことを指す
- 完成したシステムを宣伝して、より多く売るための広告活動である
- データを先頭から順に1つずつ調べて、目的のものを探す方法である
解答は 4 だぱん。
線形探索は、データを先頭から順に1つずつ調べて、目的のものを探す方法なんだぱん。本棚の端から見ていくイメージだぱん。
選択肢1は給与計算、選択肢2は請求書の事務、選択肢3は広告で、どれも違うぱん。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 給与計算のしくみではない |
| 2 | ✗ | 請求書の事務の話 |
| 3 | ✗ | 広告活動ではない |
| 4 | ✓ | 先頭から順に探す方法で正しい |
オリジナル問題2（ソート不要）
線形探索とソート（並べ替え）の関係として、最も適切なものはどれか。
- 線形探索は、並べ替え（ソート）が不要で、そのまま探せるのだ
- 線形探索は、必ず並べ替え（ソート）をしてから探すものである
- 社員の給与を計算してから、線形探索をするものだとされている
- 取引先へ請求書を郵送してから、線形探索をするものだとされる
解答は 1 だぱん。
線形探索は、並べ替え（ソート）が不要で、そのまま探せるんだぱん。バラバラに並んでいても探せるのが強みだぱん。
選択肢2の「必ずソート」、選択肢3の給与、選択肢4の請求書は、いずれも違うぱん。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✓ | ソート不要で正しい |
| 2 | ✗ | ソートは不要 |
| 3 | ✗ | 給与計算の話ではない |
| 4 | ✗ | 請求書の事務の話ではない |
オリジナル問題3（速さの目安）
線形探索の速さに関する次の記述のうち、最も適切なものはどれか。
- 線形探索は、データが多くても、つねに一瞬で探せるとされる
- 社員の給与を計算した金額に応じて、速さが決まるとされている
- データが多いと時間がかかり、最悪は全部調べる（O(n)）
- 取引先へ請求書を郵送した枚数に応じて、速さが決まるとされる
解答は 3 だぱん。
線形探索は、データが多いと時間がかかり、最悪は全部調べる（O(n)）んだぱん。「つねに一瞬」ではないので、注意だぱん。
選択肢1の「つねに一瞬」、選択肢2の給与、選択肢4の請求書は、いずれも違うぱん。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | つねに一瞬ではない |
| 2 | ✗ | 給与の金額では決まらない |
| 3 | ✓ | 多いと時間がかかる（O(n)）で正しい |
| 4 | ✗ | 請求書の枚数では決まらない |
まとめ
押さえどころ
- 🔴 線形探索 ＝ データを先頭から順に1つずつ調べて、目的のものを探す方法。
- 🔴 ソート不要 ＝ 並べ替えが要らず、データがバラバラでもそのまま探せる。
- 🟡 速さの目安 ＝ データが多いと時間がかかる（最悪は全部調べる＝O(n)）。並べ替え済みなら2分探索が速いことも。
次に学ぶ
- データ構造（配列・リスト・スタック・キュー） ── データの持ち方。探し方とあわせて押さえたい。
- 2分探索 ── 並べ替え済みのデータを、真ん中から半分ずつしぼって探す。線形探索より速いことが多い。
執筆: SikakuQuest編集部