2000個の整列済みデータから2分探索で値を探すとき、比較回数の最大値はいくつか。

解説

正解は「11」です。2分探索では1回の比較ごとに探索範囲がほぼ半分になり、範囲が1個になるまで比較を続けます。比較回数の最大値は $\lfloor {\log }_{2}n\rfloor +1$ です。$2^{10}$ は1024、$2^{11}$ は2048 なので、${\log }_{2}2000$ の整数部分は10となり、最大11回です。「10」は、範囲が1個になった最後の比較を数え忘れた値です。「1000」は、線形探索の平均比較回数（約 n/2）に近い値です。「2000」は、線形探索で目的の値が末尾にある場合や存在しない場合の最大の比較回数です。データ数が2倍になっても、2分探索の比較回数は1回しか増えません。