平成21年度 春期 基本情報技術者試験 午前 問7
テクノロジ／アルゴリズム昇順に整列されたn個のデータが配列に格納されている。探索したい値を2分探索法で探索するときの，およその比較回数を求める式はどれか。
出典：平成21年度 春期 基本情報技術者試験 午前 問7
- アlog₂n
- イ(log₂n＋1)／2
- ウn
- エn²
正解：ア
解説
2分探索法は，探索範囲を毎回半分に絞り込みながら目的の値を探す方法です。n個のデータに対して1回の比較で探索範囲がおよそ半分になるため，最大比較回数はおよそlog₂nになります。
選択肢ごとの解説
- ア正しい。2分探索法では探索範囲が1回の比較ごとに半分になるため，比較回数はおよそlog₂nです。
- イ誤り。この式は2分探索の比較回数を表す一般的な式ではありません。
- ウ誤り。nに比例する比較回数は，先頭から順に調べる線形探索の特徴です。
- エ誤り。n²に比例する比較回数は，単純な二重ループによる探索など，非効率なアルゴリズムに相当します。