バイナリサーチの計算量がO(log_2 n)となる理由

データ個数が$n$の時のバイナリサーチの計算量が$O(log_2n)$となる理由について書いてみました。

$log_an$ とは「$a$を○乗すると$n$になる」の「○」にあたる値です。
（例：$log_28$ は「$2$を○乗すると$8$になるような○」なので「$log_28 = 3$」）

バイナリサーチのアルゴリズムを簡単に書くと

1. 検索範囲（ソート済み）の中央に位置する値を検索値と比較する。
2. 検索値が中央の値より大きければ中央より右側、小さければ中央より左側を検索範囲に設定する。
3. 中央の値 == 検索値が真となるような中央の値が見つかる（または検索範囲が$1$になる）まで、1～2を繰り返す

…となります。

検索範囲が$1$になった状態とは、（検索範囲のデータ個数を$n$として）「$n$に対して$\frac{1}{2}$を繰り返し掛けていき、検索範囲のデータ個数が$1$になった状態」と言えますが、これを数式で表現すると以下のような式となります。

\begin{align}
1 &= n \times \frac{1}{2} \times \frac{1}{2} \times\quad...\quad\times　\frac{1}{2}\\
\end{align}

上の式において、「$n$に対して$\frac{1}{2}$を掛ける回数」が、データ個数が$n$の時の計算量となります。この「$\frac{1}{2}$を掛ける回数」を$x$とし、式変形して$x$を求めていきます。

\begin{align}
1 &= n \times \frac{1}{2} \times \frac{1}{2} \times\quad...\quad\times　\frac{1}{2}\\
&= n \times \Bigl(\frac{1}{2}\Bigr)^x\\
&= n \times \frac{1}{2^x}\\
&= \frac{n}{2^x}\\
両辺に2^xを掛けると\\
2^x &= n\\
\therefore x &= log_2n
\end{align}

以上、データ個数が$n$の時のバイナリサーチの計算量が$O(log_2n)$となる理由でした。