2分探索において,データの個数が4倍になると,最大探索回数はどうなるか。ここで,データの個数は十分に多いものとする。
解答 イ
【頭の準備体操】
2分探索法は，探索範囲を1/2に絞りながら目的データを探すアルゴリズム。
前提条件：あらかじめデータが昇順または降順に並んでいること。
1回目の探索で探索範囲は1/2。2回目の探索で探索範囲は更にその1/2(元の1/4)。3回目の探索で探索範囲は更にその1/2(元の1/8)･･･，と探索範囲を絞っていく。
逆に，探索回数が1回増えると探索範囲のデータの個数が2倍，2回増えると探索範囲のデータの個数が4倍になる。
(別解)
データの個数がn個の要素を探索する場合，
平均探索回数は，log2n回。
最大探索回数は，log2n＋1回。
データの個数がn個のときの最大探索回数は，log2n＋1回。
データの個数が4n個のときの最大探索回数は，log24n＋1回。
log24n＋1
＝log24＋log2n＋1
＝log222＋log2n＋1
＝2×log22＋log2n＋1
ここで，log22＝1なので，2＋(log2n＋1)
よって，2回増える。
昇順に整列されたn個のデータが配列に格納されている。探索したい値を2分探索法で探索するときの,およその比較回数を求める式はどれか。
解答 ア
【頭の準備体操】
2分探索法は，探索範囲を1/2に絞りながら目的データを探すアルゴリズム。
前提条件：あらかじめデータが昇順または降順に並んでいること。
データの個数がn個の要素を探索する場合，
平均探索回数は，log2n回。
最大探索回数は，log2n＋1回。