二分探索は、探索範囲を半分ずつ狭めながら効率よくデータを探索する方法ですが、比較回数はどのくらいになるのでしょうか？
二分探索の比較回数は計算で求められます。
データ数nの二分探索の比較回数は次のような計算式で求められます。
| 最小比較回数 | 最大比較回数 | 平均比較回数 |
|---|---|---|
| 1 | [log2n] + 1 | log2n |
[ ] は小数点以下切り捨てを意味します。
log2n ってなんですか？見たことない。
私も初めて見ました。これは数式ですか？
log(ログ)は対数と呼ばれる計算で高校の数学で学習しますが、ここでは計算できる必要はありません。
この教材では、二分探索の最大比較回数と平均比較回数は他の計算で求めます。
ただし、logを使った計算式は公式なので覚えておくと試験対策になります。
二分探索の最大比較回数と平均比較回数は、logの計算を使わずに次の式に当てはめることで求めることができます。
log2n ≒ 2x として計算できます。
2xを使った計算で、logで計算したときの近似値が求められます。
ここでは、二分探索の比較回数の計算は、logは使わず2のべき乗の計算で求めることとします。
例えば、データ数(n)が100の場合は、次のように求めます。
n=100のときの二分探索の平均比較回数と最大比較回数
2x ≦ n ≦ 2x+1
nが100なので計算式は次のようになります。
2x ≦ 100 ≦ 2x+1
ここで2のべき乗の値は次のとおりです。
| 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 210 |
|---|---|---|---|---|---|---|---|---|---|
| 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 | 512 | 1,024 |
ここで、条件を満たす計算式は次のようになります。
26 ＜ 100 ＜ 27
(64 ＜ 100 ＜ 128)
になるので、平均比較回数と最大比較回数は次のようになります。
最大比較回数：7
平均比較回数：6
これならできそう！
2のべき乗(累乗)を計算すればよいのですね。これなら簡単にできます！
