基本情報技術者試験基礎・応用
条件を読む・根拠を説明する
二分探索の前提と回数
条件を整理し、答えを選んでから解き方を確認しましょう。
昇順の相異なる1023要素から二分探索し、各比較で中央の1要素と比べる。最大比較回数はどれか。
答え・解き方を読む
10回
考える順序
- 1各比較で候補をほぼ半分にする
- 2比較回数kで扱える最大要素数は2^k−1
- 32^10−1=1023なので最大10回
選択肢ごとの理由
- 比較 · 512回
半分にする操作を1回だけ行うわけではありません。
- 比較 · 1023回
先頭からの逐次探索とは回数が異なります。
- 正解 · 10回
各比較で候補をほぼ半分にする。比較回数kで扱える最大要素数は2^k−1。2^10−1=1023なので最大10回。
- 比較 · 9回
9回で扱える最大は511要素です。