線形探索の概要
線形探索は、配列やリストの先頭から順番に要素を確認し、目的の値と一致するかを調べる最も基本的な探索手法です。データが整列されている必要はなく、途中で目的の値が見つかればそこで終了できます。正解は「目的の値が見つかるまで先頭から順に確認する」です。 (選択肢2が正しい)
正解の理由
線形探索は、配列やリストの先頭から順番に要素を確認し、目的の値と一致するかを調べる最も基本的な探索手法です。データが整列されている必要はなく、途中で目的の値が見つかればそこで終了できます。正解は「目的の値が見つかるまで先頭から順に確認する」です。
仕組み・頻出ポイント
- 未整列データにも使える一方、要素数が増えるほど確認回数がほぼ比例して増えます。
- 最悪計算量は、最後の要素まで見つからない、または存在しない場合の (O(n)) です。
- 実装が単純なので、小規模データや一度だけの探索では十分実用的なことがあります。
G検定で覚えるべきこと
二分探索との混同が頻出です。二分探索はソート済みであることを利用して範囲を半分ずつ捨てますが、線形探索は順に見るだけなので前処理を必要としません。G検定では「単純だが大規模では遅い」「ソート不要」「最悪 (O(n))」をセットで覚えると判断しやすくなります。
他の選択肢の評価
- 選択肢1: ソート必須なのは二分探索の代表的な前提で、線形探索には不要です。
- 選択肢2: 正解です。順番に比較するという動作が線形探索の本質です。
- 選択肢3: 探索範囲を半分にするのは二分探索です。
- 選択肢4: (O(1)) は要素数に依存しない定数時間で、線形探索の平均的な説明としては不適切です。
実務での見方
実務では、探索対象が小さい、または一度だけ調べればよい場合、線形探索は実装コストが低く十分な選択肢です。一方で、検索回数が多い場合は、ソート、ハッシュ表、索引構造などを検討します。G検定では、単純さと計算量のトレードオフを説明できることが重要です。
確認観点
確認観点としては、データ件数、検索回数、事前整列の有無を分けて考えます。線形探索は「準備なしで使えるが、件数に比例して遅くなる」と整理すると、他の探索手法との比較が明確になります。
結論として、この問題では「用語の定義」だけでなく、どの前提で使えるのか、どの誤解を避けるべきか、実務では何を確認するのかまで結びつけて理解することが重要です。