CO-K11｜情報Ⅰ 対策問題

正答

1

この問題のポイント

線形探索（先頭から順に調べる） を問う問題です。二分探索との効率の違いまでがセットです。

解説

探索とは、たくさんのデータの中から目的のデータを見つける処理です。線形探索は、先頭から1つずつ順番に「これか?違う。次は?」と比較していく、最も素朴な方法です。データの並び順に関係なく使えるのが長所です。

効率を比較回数で考えると、データがn個のとき、線形探索は運が悪ければ最後まで調べて最大n回、平均でもおよそn/2回の比較が必要です。データが増えれば手間もそのまま比例して増えます。

対する二分探索は、「整列済み」のデータの真ん中と比較し、目的の値が前半にあるか後半にあるかで探す範囲を半分に絞る操作を繰り返します。1000個のデータでも約10回で見つかる高速さですが、事前にデータが整列されていることが前提です。この前提条件が最頻出の引っかけポイントです。

共通テストでは、2つの探索法の手順や比較回数の違い、「二分探索が使えるのはどんなときか」が問われます。「並び順不問だが遅い=線形探索、整列済み前提で速い=二分探索」と対で覚えましょう。

選択肢の確認

1．○ 先頭から1つずつ順に比較するのが線形探索。
2．× 二分探索は中央と比較して範囲を半分ずつに絞る方法で、整列済みが前提。
3．× ハッシュ探索は値から保存場所を計算で求める方法。
4．× 幅優先探索はグラフや木構造をたどる探索法。

ここだけは覚えよう

線形=順に最大n回、二分=半分ずつに絞る — 二分探索は「整列済み」が前提条件。