線形探索
まず結論
線形探索（逐次探索）は配列の先頭から順番に目標値と比較して探す最もシンプルな探索アルゴリズムです。ソート不要で使えますが、計算量は最悪O(n)。要素数が増えると比例して遅くなります。
線形探索の動き
配列 [5, 3, 8, 1, 9, 2, 7] から「8」を探す：
Step 1: 5 と比較 → 違う
5
3
8
1
9
2
7
Step 2: 3 と比較 → 違う
5
3
8
1
9
2
7
Step 3: 8 と比較 → 一致！ 発見
5
3
8
1
9
2
7
擬似コード
// 配列 a[1..n] から key を線形探索する
手続き linearSearch(a, n, key)
i ← 1
i が n 以下の間, 繰り返す
もし a[i] = key ならば
i を返す // 発見：インデックスを返す
もし終わり
i ← i + 1
繰り返し終わり
-1 を返す // 未発見
手続き終わり
計算量
最良: O(1)（最初の要素が目標）
平均: O(n/2) = O(n)
最悪: O(n)（最後か存在しない）
特徴
✅ ソート不要
✅ 実装がシンプル
❌ データ量が多いと遅い
❌ ソート済みなら二分探索の方が速い
🎯 試験での出方
- 「先頭から順番に比較して探す探索法」→ 線形探索（逐次探索）
- 「n要素の配列を線形探索する最悪計算量」→ O(n)
- 「ソートされていないデータでも使える探索法」→ 線形探索
- 線形探索の擬似コードのトレース問題（変数iの値の変化を追う）
⚠️ よくある間違い
- 「線形探索にはソートが必要」→ ✗ ソート不要が線形探索の利点
- 「線形探索は常にO(1)」→ ✗ 最悪O(n)。二分探索がO(log n)で優れている
✍️ 確認クイズ
Q1. 線形探索の最悪計算量はどれか。
✅ 正解は③。線形探索は最悪の場合（目標が最後か存在しない）、n要素全てを比較するのでO(n)です。
Q2. 線形探索の特徴として正しいものはどれか。
✅ 正解は②。線形探索はデータの順序に依存せず、先頭から順に比較するだけなのでソート不要です。これが最大の特徴です。
Q3. 配列 [4, 2, 7, 1, 9] から「1」を線形探索する場合、何回の比較が必要か（最悪ではなく実際の回数）。
✅ 正解は③（4回）。4→違う、2→違う、7→違う、1→一致！ の順で4回比較します。インデックス0始まりなら0,1,2,3番目を確認。
Q4. 番兵法（センチネル法）を使った線形探索の目的として正しいものはどれか。
✅ 正解は②。番兵法は配列の末尾（n+1番目）に探索キーを「番兵」として格納します。これにより「i <= n」という範囲チェックが不要になり（必ず番兵に当たるため）、ループ内の条件判定が半減して処理が軽くなります。見つかった位置がn+1なら「存在しない」と判断します。
Q5. 線形探索より二分探索の方が高速になる条件として正しいものはどれか。
✅ 正解は③。二分探索はデータが整列済みであることが前提条件。整列済みならO(log n)で探索できるため、大量データでは線形探索O(n)より圧倒的に速い。例えばn=1000万なら線形は最大1000万回、二分探索は最大24回（log₂(10⁷)≈24）の比較で済みます。
Sponsor Link