基本情報技術者 予想問題｜A 第19問

解説

二分探索は1回の比較ごとに探索範囲を半分に絞るため、最大比較回数はおよそ log2 n 回である。n=8の場合、範囲は 8→4→2→1 と3回の半減で1要素に確定するため、log2 8 = 3 より最大3回となり、「3回」が正解である。2回では 2^2=4 要素までしか確定できず、4回は n=16 の場合に相当し、8回は線形探索の最悪比較回数である。二分探索は整列済みデータにのみ適用できるという前提条件も重要である。n=1000でも約10回（2^10=1024）で探索できるように、要素数が倍になっても比較回数は1回増えるだけという対数的な効率の良さを問う出題が科目Aで繰り返しなされている。