問題7
昇順に整列された n 個のデータが配列に格納されている。探索したい値を2分探索法で探索するときの，およその比較回数を求める式はどれか。
| ア | log2n |
| イ | (log2n+1)/2 |
| ウ | n |
| エ | n2 |
解答・解説を見る
解答：ア
2分探索法は，整列済みの配列から効率よくデータを探索するための方法である。
2分探索法は、整列されたデータの中央の値と対象データを比較し、それより前方にあるか後方にあるかを判断する。
前方にデータがある場合は、前半分のデータの中央のデータと比較し、後方にデータがある場合は、後半分のデータの中央のデータと比較する。
この操作を繰り返すことによって、検索する方法である。
要素数がn個の場合に2分探索法を使った場合の比較回数は，次の式で求めることができる。
| 平均比較回数 | ： | (log2 n)回 | |
| 最大比較回数 | ： | (log2 n)＋1回 |
よってアが正解である。