正答1
解説
正解は1です。
2分探索法は、整列済みのデータの中央と比較し、探索範囲を毎回半分に絞る方法です。
n件のデータでの最大比較回数は、おおよそlog_2 n回です。
【計算】
探索範囲は1回の比較ごとに1/2になります。
2^10＝1024なので、1000件は10回半分にすると1件以下になります。
したがって、最大比較回数はおよそ10回です。
【選択肢別解説】
1：○ 1000≦2^10＝1024なので、最大でおよそ10回の比較で見つかります。
2：× 46回は2分探索の最大比較回数と一致しません。
46回もかかるのは、2の46乗ほどの件数がある場合に相当します。
3：× 500回は、先頭から順に調べる線形探索の平均比較回数（n/2）です。
4：× 1000回は、線形探索の最大比較回数（n回）です。
【ポイント】
2分探索の比較回数はlog_2 n、線形探索は平均n/2・最大nです。
2^10≒1000は計算問題で頻繁に使うので覚えておきます。