昇順に整列されたn 個のデータが配列に格納されている。
探索したい値を2分探索法で探索するときの、およその比較回数を求める式はどれか。
ア | log2n |
イ | (log2n +1)/2 |
ウ | n |
エ | n2 |
答え ア
【解説】
2分探索法は1回探索を行うごとに、探索する範囲を半分にしながら行っていくので、m 回の探索を行い探索するデータがなかったときの、データ配列の大きさは2m である。
したがって、n 個のデータ配列についての探索の回数はlog2n (ア)になる。
【キーワード】
・2分探索法