２分検索とは
「検索」は、複数のデータの中から目的のデータを探し出すプログラムである。
「二分検索」は、規則的に並んだデータを二分割にしてデータを絞り込み、最終的にデータが１件なるまで繰り返すことによって、目的のデータを探し出す検索方法。
このとき、理論上$N$ 件のデータがあるとき、$１$になるまで繰り返し$２$で割った回数$n$ が、最大検索回数となる。
よって以下の数式で表すことができる。
$$N\times\underbrace{\frac{1}{2}\times\frac{1}{2}\times\frac{1}{2}\times\frac{1}{2}\cdots}_{n}=1$$
$$N\times\left(\frac{1}{2}\right)^n=1$$
$$N=2^n$$
すなわち、分割回数$𝑛$は以下のように表される。これが、最大検索回数となる。
$$n = \log_{2} N$$
これをコンピュータで計算する際、多くのプログラミング言語では関数として$\log_{10} 𝑥$と$\log_{𝑒} 𝑥$しか、用意されていないため、以下のように「底の変換公式」を用いて求める。
$$n = \log_{2} N=\frac{\log_{10}N}{\log_{10}2}=\frac{\log_{e}N}{\log_{e}2}$$
たとえば、$1,000$ 件のデータがあった場合、
$$n = \log_{2}1000=\frac{\log_{10}1000}{\log_{10}2}=\frac{3}{0.30102\cdots}=9.965784285\cdots$$
となる。$9.965\cdots$という値は、$9$ 回ともう$1$ 回の検索が必要であることを示しており、$1,000$件のデータを$1$ 件ずつ$1,000$回探す場合に比べて、最大$10$ 回の検索で目的のデータが探し出すことを可能にする。