2分探索法の比較回数

問題

昇順に整列された n 個のデータが配列に格納されている。
探索したい値を2分探索法で探索するときの,およその比較回数を求める式はどれか。

回答

log2n

解説

2分探索法は、整列されたデータの中央の値と対象データを比較し、それより前方にあるか後方にあるかを判断する。
前方にデータがある場合は、前半分のデータの中央のデータと比較し、後方にデータがある場合は、後半分のデータの中央のデータと比較する。
この操作を繰り返すことによって、検索する方法である。
2分探索法での比較回数は、log2n である。

覚えましょう~

2分探索法の平均探索回数とくれば データがN件の場合→logN回
2分探索法の最大探索回数とくれば データがN件の場合→logN+1回

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License