二分探索の回数
整列済みの1,024件のデータから二分探索で目的の値を探すとき、最大の比較回数の目安として最も適切なものを1つ選べ（1,024 = 2の10乗）。
- A
約32回
- B
約512回
- C
約1,024回
- D
約10回
正解と解説を見る
正解：D
二分探索は整列済みのデータを1回の比較ごとに半分に絞るので、比較回数は log2(n) 程度で、最悪でも log2(n) + 1 回、1,024件なら11回程度になる。先頭から順に調べる線形探索の回数(最大 n 回、平均 n ÷ 2 回)と取り違えやすい。
| 比較の回数 | 残る候補の数 |
|---|---|
| 0 | 1,024 |
| 1 | 512 |
| 5 | 32 |
| 10 | 1 |
- A
誤り。1,024の平方根で、半分に絞っていく回数とは関係がない。
- B
誤り。先頭から順に調べる線形探索で、平均的にかかる回数の目安(n ÷ 2)。
- C
誤り。線形探索の最大の比較回数。
- D
正しい。1回ごとに探す範囲が半分になるので、10回程度(最悪でも11回)で絞り込める。
このサイトの問題は、各試験の公開されている出題範囲に沿って作ったオリジナルの模擬問題です。本試験の問題ではありません。一般社団法人データサイエンティスト協会・一般財団法人統計質保証推進協会の公式サービスではありません。