CO-S11｜情報Ⅰ 対策問題

正答

1

この問題のポイント

二分探索の効率（半分ずつ絞る） を問う問題です。「何回半分にすると1になるか」を数えられるかがカギです。

解説

二分探索は、整列済みのデータの真ん中と目的の値を比較し、「目的はどちら側にあるか」で探す範囲を半分に絞る探し方です。辞書で単語を探すとき、真ん中あたりを開いて前か後ろかを判断するのと同じ発想です。1回の比較で範囲が半分になるのが最大の特徴です。

1024個から始めて、範囲が1個になるまで半分にしていきます。

1. 1回目の比較: 1024 → 512
2. 2回目: 512 → 256
3. 3回目: 256 → 128
4. 4回目: 128 → 64
5. 5回目: 64 → 32
6. 6回目: 32 → 16
7. 7回目: 16 → 8
8. 8回目: 8 → 4
9. 9回目: 4 → 2
10. 10回目: 2 → 1

半分にする操作を10回行うと1個に絞れます。2を10回掛けると2¹⁰=1024になることの裏返しで、この回数をlog₂1024=10と表します。一方、先頭から順に調べる線形探索なら最悪1024回の比較が必要です。

データが増えるほど差は劇的になり、100万件でも二分探索なら約20回で済みます(2²⁰≒100万)。ただし二分探索は「データが整列済み」であることが前提です。共通テストでは「およそ何回か」という概算や、線形探索との比較の形で問われます。2¹⁰=1024は暗記しておくと即答できます。

選択肢の確認

1．○ 2¹⁰ = 1024 なので、半分にする操作は約10回で済む。
2．× 約1024回は線形探索で最悪の場合(末尾にある・存在しない)の回数。
3．× 512は1回比較したあとの「残りの範囲」であって比較回数ではない。
4．× 32は2⁵との混同。2⁵=32では1024に届かない。

ここだけは覚えよう

二分探索は1回で範囲が半分、2¹⁰=1024なら約10回 — 前提は「整列済みのデータ」。