二分探索の比較回数の増分
整列済み配列に対する二分探索で、要素数を 1024 から 4096 に増やしたとき、最悪の場合の比較回数はおよそ何回増えるか。
解説を見る
二分探索の最悪比較回数はおよそ log2(要素数)。log2(1024)=10、log2(4096)=12 なので増分は 12-10 = 2 回。要素数が4倍(=2の2乗倍)になっても、対数的にしか増えないのが二分探索の利点である。
誤答の解説
B要素数が4倍だから比較も4倍・4回増、という線形の発想。二分探索は対数的にしか増えない。
C4096-1024=3072 は要素数の差。線形探索の発想で、二分探索の性質を使っていない。
D12 は 4096 側の総比較回数(log2 4096)。問われているのは増分なので 12-10。
ヒント
・二分探索の比較回数は要素数の対数に比例する。
・4096 = 4 × 1024 = 2^2 × 2^10。