線形探索法
更新日:
用語解説
線形探索法は、データの先頭から順に1つずつ比べて、目的の値を探す方法です。
■ 試験で押さえるポイント
データが整列されていなくても使えます。
比較の回数は、平均でn/2回、最悪でn回です（計算量O(n)）。
末尾に探す値を置く番兵を使うと、終わりの判定を省けます。
探索法 | 前提 | 平均比較回数・計算量 |
|---|---|---|
線形探索法 | なし（未整列でよい） | 約 n/2 回、O(n) |
2分探索法 | データが整列済み | 約 log₂n 回、O(log n) |
ハッシュ表探索法 | ハッシュ関数で格納位置を計算 | 衝突がなければ1回、O(1) |
■ 過去問での着眼点
整列が不要な代わりに、データが多いと時間がかかる点を押さえます。
例: 1,000件の名簿から、先頭から順に名前を比べて探します。