1. 準備編
> やること
- 二分探索法の平均探索回数の厳密な値を求めることのできる公式(一般式)を導出する。
- 情報処理技術者試験の(昔の？)参考書や過去問解説で公式のように記載されている、二分探索法の平均探索回数の近似値 $\bigl[\log_2 n\bigr]$ の妥当性を確認する。
> 前提
-
二分探索法の最大探索回数は $\bigl[\log_2 n\bigr]+1$ である。
-
データ件数$n$ について、 $n\geqq2$ の場合を考える。
-
アルゴリズムの設定
- 探している値と基準値(中央値)の大小比較を行う。
- 基準値と一致した場合、残りの要素数にかかわらず、その時点で探索を終了する。
- 基準値と一致しなかった場合、本来の実装では基準値を除いて範囲の絞り込みを行うが、確率計算の都合上、基準値は除かない。
- データの中に探している値と一致するデータが必ず1つ存在することを前提とする。
そうでなければ平均値は一意に定まらない。
> 具体例でイメージ
まずは具体的な値で平均探索回数の計算方法のイメージを掴もう。
例えば、$n=16$ のときの平均探索回数はどうなるか。
この例では、データの内容は1から16までの整数が1つずつ揃っているとするが、データの内容と平均探索回数は無関係である。
- $1$ 回目に見つかるのは $2^0=1$ 個
- $2$ 回目に見つかるのは $2^1=2$ 個
- $3$ 回目に見つかるのは $2^2=4$ 個
- $4$ 回目に見つかるのは $2^3=8$ 個
- $5$ 回目に見つかるのは、残りの $16-\bigl(1+2+4+8\bigr)=1$ 個
この先の立式に必要な期待値の考え方を簡単化するため、これを別の例に置き換えて考えてみる。
16人がある点数制のゲームを行った。
- $1$ 点を取った人が $1$ 人
- $2$ 点を取った人が $2$ 人
- $3$ 点を取った人が $4$ 人
- $4$ 点を取った人が $8$ 人
- $5$ 点を取った人が $1$ 人
という結果になったとする。
まず、$16$ 人で合計何点を獲得したか。
各点数にその点数を取った人数をかけたものを合計すればよいので、
1{\small(点)}\cdot1{\small(人)} + 2{\small(点)}\cdot2{\small(人)} + 3{\small(点)}\cdot4{\small(人)} + 4{\small(点)}\cdot 8{\small(人)} + 5{\small(点)}\cdot1{\small(人)} = 54{\small(点)}
次に、$1$ 人あたり平均して何点を獲得したか。
合計値を $16$ 人で割ればよいので、
\frac{54}{16} = 3.375{\small(点)}
となる。
ここまでを最初のデータ数が $16$ 個の場合の二分探索法に当てはめると、単位が変わるだけで全く同じ計算になり、平均して $3.375$ 回目で見つかることがわかる。
2. 厳密な平均探索回数
具体例で計算方法のイメージを掴んだので、いよいよデータ件数が $n$ の場合の厳密な平均探索回数を数式に表してみる。
> 立式
データ数が$n$のときの、最大探索回数を $k=\bigl[\log_2 n\bigr]+1$ とおく。
- $1$ 回目に見つかるのは $2^0$ 個
- $2$ 回目に見つかるのは $2^1$ 個
- $3$ 回目に見つかるのは $2^2$ 個
$\vdots$ - $\bigl(k-1\bigr)$ 回目に見つかるのは $2^{k-2}$ 個
- $k$ 回目に見つかるのは、残りの $n-\bigl(2^0+2^1+2^2+ \cdots +2^{k-2}\bigr)$ 個
平均探索回数は、ざっくりとした日本語で表すと次のように計算できることがお分かりだと思う。
平均探索回数 = \frac{ (探索回数\times見つかる個数) の合計値 }{n}
$1$ 回目から $(k-1)$ 回目までに見つかる個数の計算には一定の法則性が見出される。
ただし $k$ 回目、すなわち最後に見つかる個数だけは、$1$ 回目～ $(k-1)$ 回目までに見つかる個数をデータ数全体から引いたもの、すなわち "残り" となる。
これに注意をしながら数式で表すと、データ件数が $n$ のときの厳密な平均探索回数 $μ(n)$ は
\begin{eqnarray}
μ(n) &=&\frac{1\cdot2^0+2\cdot2^1+3\cdot2^2+\cdots+\bigl(k-1\bigr)\cdot2^{k-2}+k\cdot \Bigl\{ n-\bigl(2^0+2^1+2^2+ \cdots +2^{k-2}\bigr) \Bigr\} } {n} \\
&=&\frac{\sum\limits_{j=1}^{k-1}\bigl(j\cdot2^{j-1}\bigr) + k \cdot \biggl\{n-\sum\limits_{j=1}^{k-1}2^{j-1}\biggr\}}{n}
\end{eqnarray}
となる。
> 式変形
シグマ記号$\bigl(\sum \bigr)$を使った計算は、公式等を使ってシグマ記号なしで表すことができる。
ここで
\begin{eqnarray}
A &=& \sum\limits_{j=1}^{k-1}\bigl(j\cdot2^{j-1}\bigr),\
B &=& \sum\limits_{j=1}^{k-1}2^{j-1}
\end{eqnarray}
とおくと、平均探索回数 $μ(n)$ は
μ(n)=\frac{A+k\bigl\{n-B\bigr\}}{n}
と表せる。
以下では $A,B$ それぞれに公式等を適用し、シグマ記号のない形に変形する。
>> (1) Bの変形
$B$については、等比数列の和の形になっているので、等比数列の和の公式
\sum\limits_{k=1}^{n}ar^{k-1} = \frac{a\bigl(r^n-1\bigr)}{r-1}
を適用し、
B = \sum\limits_{j=1}^{k-1}2^{j-1} = \frac{1\bigl(2^{k-1}-1\bigr)}{2-1} = 2^{k-1}-1
と変形できる。
>> (2) Aの変形
$A$については、等差×等比の和の形になっていて、等比数列の和を応用した定番の解法があるので、これに従う。
\begin{array}{rrrr}
&A=& 1\cdot2^0 & + & 2\cdot2^1 + 3\cdot2^2 + \cdots\cdots\cdots + (k-1)\cdot 2^{k-2} \\
-\large{)}&-2A=&&&1\cdot2^1 + 2\cdot2^1 + \cdots\cdots\cdots +(k-2)\cdot2^{k-2}&+(k-1)\cdot2^{k-1}\\
\hline
&-A=& 1\cdot2^0 &+& 1\cdot2^1 + 1\cdot2^1 + \cdots\cdots\cdots + \ \ \ \ \ \ 1 \ \ \ \ \cdot2^{k-2} &-(k-1)\cdot2^{k-1}
\end{array}
\begin{eqnarray}
-A &=& \sum\limits_{l=1}^{k-1}1\cdot2^{l-1} -(k-1)\cdot2^{k-1} \\
\end{eqnarray}
等比数列の和の公式を適用して
\begin{eqnarray}
-A &=& \frac{1\cdot\bigl(2^{k-1}-1\bigr)}{2-1} -(k-1)\cdot2^{k-1} \\
\end{eqnarray}
A = 2^{k-1}\bigl(k-2\bigr)+1
となる。
>> (3) 仕上げ
よって、
\begin{eqnarray}
μ(n)=\frac{A+k\bigl\{n-B\bigr\}}{n}
&=& \frac{\biggl\{2^{k-1}\bigl(k-2\bigr)+1\biggr\}+k\biggl\{n-\bigl( 2^{k-1}-1 \bigr)\biggr\}}{n}\\
&=& k - \frac{2^k-k-1}{n}
\end{eqnarray}
となり、シグマ記号のない形に変形できた。
> 厳密な平均探索回数【まとめ】
改めて、
二分探索法で、データ件数が$n(n\geqq2)$のとき、
最大探索回数を $k=\bigl[\log_2 n\bigr]+1$ とおくと、
厳密な平均探索回数 $μ(n)$ は
μ(n) = k - \frac{2^k-k-1}{n}
で求まる。
3. 平均探索回数の近似値
基本情報技術者試験などの(昔の？)参考書や過去問解説で、二分探索法の平均探索回数(平均比較回数)について、公式のように登場するのは
\bigl[\log_2 n\bigr]
である。
これは上記の厳密な公式とは違い、あくまで平均探索回数の"近似値"である。
括弧 $\bigl[ \ \bigr]$ はガウス記号といい、
$\bigl[a\bigr]$ は、$a$を超えない最大の整数、つまり$a$の小数部分を切り捨てた値を表す。
> [log2_n]の誤差
$\bigl[\log_2 n\bigr]$ が、平均探索回数の近似値として、精度がどの程度なのかを確認する。
具体的には、 近似値 $\bigl[\log_2 n\bigr]$ と、先に示した厳密な値 $μ(n)$ との間に生じる、誤差の範囲を求めてみる。
>> (1) 平均探索回数が満たす条件
まず、最大探索回数 $k$ は
2^{k-1} \leqq n \leqq 2^{k}-1
を満たす。
(これは何を言っているのかというと、具体値で考えてみると、
最大探索回数が $4$ となるデータ件数 $n$ は、
$2^{4-1} \leqq n \leqq 2^{4}-1$ すなわち $n=8,9,10,11,12,13,14,15$ である、というようなことである。)
$n = 2^{k-1}$(最小)のとき、厳密な平均探索回数は
\begin{eqnarray}
μ(2^{k-1})&=&k - \frac{2^k-1-k}{ 2^{k-1}} \\\
&=&k-1+\frac{k+1}{2^{k-1}}-1
\end{eqnarray}
となり、
$n = 2^{k}-1$(最大)のとき、厳密な平均探索回数は
\begin{eqnarray}
μ(2^{k}-1)&=&k - \frac{2^k-1-k}{2^{k}-1} \\\
&=&k-1+\frac{k}{2^{k}-1}
\end{eqnarray}
となるので、
最大探索回数が $k$ のとき、厳密な平均探索回数$μ(n)$は
μ(2^{k-1}) \leqq μ(n) \leqq μ(2^{k}-1) \\
\therefore k-1+\frac{k+1}{2^{k-1}}-1 \leqq μ(n) \leqq k-1+\frac{k}{2^{k}-1}
を満たすことが分かる。
>> (2) 誤差
次に、$μ'(n) = k-1$ とおき、各辺から $μ'(n)$ を引くと
\frac{k+1}{2^{k-1}}-1 \leqq μ(n)-μ'(n) \leqq \frac{k}{2^{k}-1}
となる。
ここで
C = \frac{k+1}{2^{k-1}}-1, \ D = \frac{k}{2^{k}-1}
とおくと、
もろもろ証明を頑張って…
Cについて
方針：極限(と二項定理)を用いて、$C$ が $-1$ 以上であることを証明する。
\begin{eqnarray}
\lim_{k \to \infty} \biggl( C+1 \biggr)
&=& \lim_{k \to \infty} \frac{k+1}{2^{k-1}} \\
&=& 2\lim_{k \to \infty} \frac{k+1}{2^{k}} \\
&=& 2\lim_{k \to \infty} \biggl( \frac{k}{2^{k}} + \frac{1}{2^{k}} \biggr) \\
&=& 2\lim_{k \to \infty} \frac{k}{2^{k}}
\end{eqnarray}
ここで、二項定理より
\begin{eqnarray}
2^k = (1+1)^k &=& \sum\limits_{l=0}^{k} {}_k \mathrm{C}_l \cdot 1^{k-l}\cdot1^{l} \\
&=& 1 + k + \frac{k\bigl(k-1\bigr)}{2\cdot1} + \cdots\cdots \\
&>& \frac{1}{2} k\bigl(k-1\bigr)
\end{eqnarray}
となるから、
両辺の逆数をとり、両辺に $k$ をかけて
0 < \frac{k}{2^k} < \frac{2}{k-1}
が成り立つ。
右端の辺について
\lim_{k \to \infty} \frac{2}{k-1} = 0
なので、(はさみうちの原理より)
\lim_{k \to \infty} \frac{k}{2^k} = 0
ゆえに
C+1 \geqq 0 \\
\therefore C \geqq -1
Dについて
方針：数学的帰納法を用いて、$D$ が $1$ 以下であることを示す。
まず、$k$ が $k \geqq 1$ の整数であるときに、$k+1 \leqq 2^k $ が成り立つことを証明する。
$k=1$ のとき
1+1=2^1
となり、成り立つ。
$k=\ell$ のとき、$\ell+1 \leqq 2^\ell$ が成り立つと仮定すると、
$k=\ell+1$のとき
(\ell+1)+1 = \ell+2 < 2\bigl(\ell+1\bigr) \leqq 2\cdot2^\ell = 2^{\ell+1} \\
\therefore (\ell+1)+1 \leqq 2^{\ell+1}
が成り立つ。
以上から、$k$ が $k \geqq 1$ の整数であるときに、$k+1 \leqq 2^k \ \cdots $ ① が成り立つことが証明できた。
① の両辺から $1$ を引いて
k \leqq 2^{k} -1
両辺を $2^{k}-1$ で割って
\frac{k}{2^k-1} \leqq 1 \\
\therefore D \leqq 1
以上をまとめると
-1 \leqq C, \ D \leqq 1
が成り立つので、
-1 \leqq C \leqq μ\bigl(n\bigr)-μ'\bigl(n\bigr) \leqq D \leqq 1 \\
\therefore -1 \leqq μ\bigl(n\bigr)-μ'\bigl(n\bigr) \leqq 1 \\
辺々に $-1$ をかけて
-1 \leqq μ'\bigl(n\bigr)-μ\bigl(n\bigr) \leqq 1
となる。
$μ'\bigl(n\bigr)-μ\bigl(n\bigr)$ は、平均探索回数の近似値が厳密な値からどれくらい離れているか、つまり誤差を意味する。
よってこの式から、
平均探索回数の近似値 $\bigl[\log_2 n\bigr]$は、厳密な値との誤差が $±1$ 以下になる。
ということが分かった。
> 平均探索回数の近似値【まとめ】
二分探索法で、平均探索回数の近似値が$\bigl[\log_2 n\bigr]$とされていることについては、
厳密な平均探索回数との誤差が $±1$以下 となる程度の妥当性がある。
補足：誤差が$±0.5$以下の四捨五入とは違う！
4. 参考
> データ
いくつかの具体的なデータ件数における、平均探索回数の厳密な値と近似値の誤差を示しておく。
おまけで四捨五入についても示しておくので、近似値≠四捨五入であることも実感してほしい。
- n：データ件数 $n$
- 最大：最大探索回数 $k=[log_2 n] + 1$
- 近似値：平均探索回数の近似値 $μ'(n) = k-1 = [log_2 n]$
- 厳密：厳密な平均探索回数 $μ(n) = k - \frac{2^k-k-1}{n}$
- 誤差：平均探索回数の近似値と厳密な値との差 $μ'(n)-μ(n)$
- 四捨五入：厳密な平均探索回数 $μ(n)$ を小数第1位で四捨五入した値
- ズレ：近似値と四捨五入の結果にズレがあるかどうか
| n | 最大 | 近似値 | 厳密 | 誤差 | 四捨五入 | ズレ |
|---|---|---|---|---|---|---|
| 2 | 2 | 1 | 1.5000 | -0.5000 | 2 | 有 |
| 3 | 2 | 1 | 1.6667 | -0.6667 | 2 | 有 |
| 4 | 3 | 2 | 2.0000 | 0.0000 | 2 | - |
| 5 | 3 | 2 | 2.2000 | -0.2000 | 2 | - |
| 6 | 3 | 2 | 2.3333 | -0.3333 | 2 | - |
| 7 | 3 | 2 | 2.4286 | -0.4286 | 2 | - |
| 8 | 4 | 3 | 2.6250 | +0.3750 | 3 | - |
| 9 | 4 | 3 | 2.7778 | +0.2222 | 3 | - |
| 10 | 4 | 3 | 2.9000 | +0.1000 | 3 | - |
| 11 | 4 | 3 | 3.0000 | 0.0000 | 3 | - |
| 12 | 4 | 3 | 3.0833 | -0.0833 | 3 | - |
| 13 | 4 | 3 | 3.1538 | -0.1538 | 3 | - |
| 14 | 4 | 3 | 3.2143 | -0.2143 | 3 | - |
| 15 | 4 | 3 | 3.2667 | -0.2667 | 3 | - |
| 16 | 5 | 4 | 3.3750 | +0.6250 | 3 | 有 |
| 31 | 5 | 4 | 4.1613 | -0.1613 | 4 | - |
| 32 | 6 | 5 | 4.2188 | +0.7812 | 4 | 有 |
| 63 | 6 | 5 | 5.0952 | -0.0952 | 5 | - |
| 64 | 7 | 6 | 5.1250 | +0.8750 | 5 | 有 |
| 127 | 7 | 6 | 6.0551 | -0.0551 | 6 | - |
| 128 | 8 | 7 | 6.0703 | +0.9297 | 6 | 有 |
| 255 | 8 | 7 | 7.0314 | -0.0314 | 7 | - |
| 256 | 9 | 8 | 7.0391 | +0.9609 | 7 | 有 |
| 511 | 9 | 8 | 8.0176 | -0.0176 | 8 | - |
| 512 | 10 | 9 | 8.0215 | +0.9785 | 8 | 有 |
| 1023 | 10 | 9 | 9.0098 | -0.0098 | 9 | - |
| 1024 | 11 | 10 | 9.0117 | +0.9883 | 9 | 有 |
| 2047 | 11 | 10 | 10.0054 | -0.0054 | 10 | - |
| 2048 | 12 | 11 | 10.0063 | +0.9937 | 10 | 有 |
| 4095 | 12 | 11 | 11.0029 | -0.0029 | 11 | - |
| 4096 | 13 | 12 | 11.0034 | +0.9966 | 11 | 有 |
| 8191 | 13 | 12 | 12.0016 | -0.0016 | 12 | - |
| 8192 | 14 | 13 | 12.0018 | +0.9982 | 12 | 有 |
| 16383 | 14 | 13 | 13.0009 | -0.0009 | 13 | - |
| 16384 | 15 | 14 | 13.0010 | +0.9990 | 13 | 有 |
| 32767 | 15 | 14 | 14.0005 | -0.0005 | 14 | - |
| 32768 | 16 | 15 | 14.0005 | +0.9995 | 14 | 有 |
| 65535 | 16 | 15 | 15.0002 | -0.0002 | 15 | - |
| 65536 | 17 | 16 | 15.0003 | +0.9997 | 15 | 有 |
| 131071 | 17 | 16 | 16.0001 | -0.0001 | 16 | - |
| 131072 | 18 | 17 | 16.0001 | +0.9999 | 16 | 有 |
| 100 | 7 | 6 | 5.8000 | +0.2000 | 6 | - |
| 1000 | 10 | 9 | 8.9870 | +0.0130 | 9 | - |
| 10000 | 14 | 13 | 12.3631 | +0.6369 | 12 | 有 |
| 100000 | 17 | 16 | 15.6895 | +0.3105 | 16 | - |
| 1000000 | 20 | 19 | 18.9514 | +0.0486 | 19 | - |
| 10000000 | 24 | 23 | 22.3223 | +0.6777 | 22 | 有 |
| 100000000 | 27 | 26 | 25.6578 | +0.3422 | 26 | - |
※小数第4位まで表示している。(小数第5位で四捨五入)
> 参考文献
二分探索法の平均探索回数について 佐藤道一
※本記事の説明を端折るとこうなるよ