用語集
線形探索せんけいたんさく
データを先頭から順に走査して目的の値を探す単純な探索アルゴリズム。
データを先頭から順に走査して目的の値を探す単純な探索アルゴリズム。
線形探索（逐次探索）は、データを先頭から 1 つずつ順に調べて、目的の値を探す最も単純な探索アルゴリズムです。
| 観点 | 線形探索 | 2 分探索（2 分探索） |
|---|---|---|
| 計算量 | O(N) | O(log N) |
| 前提 | 整列不要 | 整列済みが必要 |
| 速さ | 遅め | 速い |
たとえば 100 件のデータを探すとき、運が悪いと 100 回比較が必要です（O(n)）。整列されていなくても使える手軽さが利点ですが、データが多いと遅くなります。整列済みなら 2 分探索のほうが圧倒的に高速です。
試験では 線形探索（先頭から順・O(N)・整列不要）と 2 分探索（半分ずつ・O(log N)・整列必須）の対比が頻出です。