昇順に整列された 1000 個のデータから、二分探索で目的のデータを探す。各回で中央の要素と比較して探索範囲を半分に絞るとき、最悪の場合に必要な比較回数は、次のうちどれか。
正解・解説を確認する
解答正解 2
二分探索は 1 回の比較で探索範囲が約半分になるので、n 個のデータに対する最悪の比較回数は ⌊log₂n⌋＋1 回、計算量は O(log n) である。n＝1000 では 2⁹＝512 と 2¹⁰＝1024 の間にあるため 10 回となる。データが整列済みであることが前提で、未整列のデータには使えない。
選択肢ごとの判定
1log₁₀1000 の値。二分探索は範囲を半分に絞るので、底は 2 である。
2正しい。2⁹＝512＜1000≦2¹⁰＝1024 より、最悪でも 10 回で見つかるか、存在しないことが判明する。
3√1000 の値。計算量が O(√n) になるのは別の探索法である。
4線形探索（先頭から順に調べる方法）の平均的な比較回数 n／2。
5線形探索の最悪の比較回数。二分探索では整列済みであることを利用して大幅に減らせる。