問題 No.3133
昇順に整列されたデータに対して二分探索を行うシステムを設計している。要素数が最大で65,536件に達する場合、最悪のケースにおいて必要な比較回数の上限として正しいものはどれか。
【正解の解説】
16回
これは辞書で言葉を探すときに、真ん中を開いて目的の単語が前か後ろかを確認し、不要な半分をどんどん捨てていく作業と同じです。1回調べるたびに候補の数が「2のn乗」のように半分になっていくため、2の16乗が65,536になることから、たった16回の質問でどんなに遠くにあるデータも確実に探し当てることができます。全件を順番に調べる線形探索と比べると、圧倒的な速さを誇る非常に効率的なアルゴリズムの本質を表しています。
スポンサーリンク
【その他の選択肢の解説】
32回
初学者がやりがちな計算ミスとして、データの数そのものを単純に割ったり、指数と掛け算を混同して「65,536の半分だから…」と考えてしまう罠があります。二分探索は毎回「半分にする」という爆発的な削減効果があるため、足し算や引き算ではなく「何回半分に割ったら1になるか（底を2とする対数）」を計算する必要がある点をしっかりと押さえておくことが重要です。
64回
コンピュータの世界では2の倍数が基準になることが多く、64（2の6乗）という数字もよく見かけるため、なんとなく直感で選んでしまうように仕組まれています。しかし、65,536という数は2の16乗であるため、どれだけデータが増えても比較回数は16回で済みます。データ量が爆発的に増えても必要な回数が少ししか増えないという二分探索の凄さを感覚的に理解することが鍵となります。
65,536回
二分探索の仕組みを理解しておらず、すべてのデータをしらみつぶしに調べる「線形探索」の最大回数と勘違いさせるための典型的な出題者の罠です。もし二分探索でデータ数と同じ65,536回も比較していたら、範囲を半分に絞り込んでいる意味が全くなくなってしまいます。アルゴリズムごとの特徴と、効率性の違いを整理して覚えることが合格への近道です。