問題 No.3085
要素数が1,024件の昇順に整列された配列に対して、二分探索を用いて特定の値を探す場合、最大で何回の要素比較を行えば探索が完了するか。
【正解の解説】
10回
辞書から目的の単語を探すとき、ページを常に真ん中でパカッと開いて「前か後ろか」を絞り込んでいくのと同じ仕組みです。1,024ページの本であっても、「1回めを開けば512ページ分、2回めを開けば256ページ分…」と驚異的なスピードで範囲が半分になっていくため、わずか10回めくれば必ずお目当てのページにたどり着けます。これが二分探索の圧倒的な爆発力です。
スポンサーリンク
【その他の選択肢の解説】
9回
初学者が計算ミスや「2の10乗」と「2の9乗」の数字の記憶違いで最も引っかかりやすい定番の罠です。512件なら9回、それが倍の1,024件になったのだから1回増えて10回になる、という累乗の感覚をしっかり押さえておかないと、この手の問題でうっかり選択してしまい失点する原因になります。
1,024回
これは、きちんと言い換えると「並び替えられていない名簿の最初からしらみつぶしに名前を確認していく方法」である線形探索の罠です。今回は昇順に綺麗に並んでいるデータなので、わざわざ泥臭く1つずつ探す必要はありません。二分探索の賢い仕組みを忘れて、データ件数そのものがそのまま答えになると勘違いさせるための出題者の巧妙な引っかけです。
512回
人間が直感的に「1,024件の半分だから512件（回）だろう」と考えてしまう心理の隙を突くための誤答選択肢です。二分探索は「1回調べるごとに残りの候補が1/2になる」という割り算の繰り返しを行うため、探す回数は「割る回数＝累乗の指数（2の10乗の10）」になります。件数そのものを半分にした数字とは全く計算の概念が異なるので注意が必要です。