アルゴリズム・プログラミング計算問題
要素数 n = 1024 の整列済み配列に対して二分探索を行う場合、最大何回の比較で目的の要素を見つけることができるか(または存在しないことを確認できるか)。
A.8回
✗ 8回では不十分です。2^8 = 256 であり、1024要素を探索するには足りません。
B.10回← 正解
✓ 正解です。二分探索の最大比較回数は ⌈log₂ n⌉ で、log₂ 1024 = 10 回となります。
C.12回
✗ 12回は多すぎます。2^10 = 1024 のため、10回で十分にカバーできます。
D.16回
✗ 16回は誤りです。2^16 = 65536 であり、1024要素には過大な値です。