CO-S34｜情報Ⅰ 対策問題

正答

1

この問題のポイント

線形探索の比較回数（最悪と平均） を問う問題です。最良・平均・最悪の3つの場合を区別できるかがカギです。

解説

線形探索(逐次探索)は、先頭から順に1つずつ「これは目的の値か」と比較していく、最も素朴な探し方です。整列されていないデータでも使えるのが利点ですが、比較回数はデータ数に比例します。

n=100個の場合を、場合分けして考えます。

1. 最良の場合: 目的の値が先頭にある → 1回の比較で見つかる
2. 最悪の場合: 目的の値が末尾にある、または存在しない → 100回の比較が必要
3. 平均の場合: 目的の値がどこにあるかは均等にあり得るので、およそ真ん中 → 約50回(n/2回)

よって「最悪100回、平均およそ50回」が正しい記述です。「常にちょうど100回」は誤りで、途中で見つかればそこで探索は終わります。また「必ず7回以内」は二分探索の話です(2⁷=128>100なので、整列済みなら7回で絞り込める)。

共通テストでは、線形探索と二分探索の比較回数を対比させる問題が定番です。「線形は最悪n回・平均n/2回、二分はlog₂n回。ただし二分探索は整列済みが前提」と、回数と前提条件をセットで整理しておきましょう。

選択肢の確認

1．○ 最悪でn=100回、平均で約n/2=50回。
2．× 途中で見つかればそこで終わるので「常にちょうど100回」ではない。
3．× 7回以内で必ず見つかるのは整列済みデータへの二分探索。
4．× 線形探索の比較回数はデータの個数に比例する。

ここだけは覚えよう

線形探索は最悪n回・平均n/2回 — 「必ず少ない回数で」と来たら二分探索(整列済み前提)との混同を疑う。