問題
昇順に整列された n 個のデータが配列に格納されている。探索したい値を 2 分探索法で探索するときの、およその比較回数を求める式はどれか。
選択肢
- 1log₂n
- 2(log₂n+1)/2
- 3n
- 4n²
正解
1. log₂n
詳しい解説を見る解説を閉じる
解説
2 分探索法は探索範囲を毎回半分に絞り込むため、n 個のデータに対する比較回数はおよそ log₂n に比例する。よって「ア」が正しい。線形探索(逐次探索)は平均で n/2 回、最悪 n 回の比較が必要で計算量が大きい。(出典: 平成21年度 春期 基本情報技術者試験 午前 問7)
一問一答
科目A 180問+科目B 60問