二分探索法

二分探索法(バイナリーサーチ)とは探索アルゴリズムの一つで、ソート済みの配列を2分割し、探索したい数値がどちらに入っているかを探していく方法です。よく引き合いに出されるのが線形探索法で、一つずつ端から検索していく同手法に比べ、大幅に探索回数を減らす事ができます。

■具体例
いま、1から100までの数値の中から一つだけ数字を指定し、それを二分探索法によって見つけ出します(二分探索法は何を指定されたかは解らない)。ここでは100を指定したとします。

先ず以下の様に配列を2分割し、指定の数字がどちらに入っているかを調べます。この場合は50以下の中に入っていないことを確認できました。

次に、50～100までの数値を以下の様に2分割し、指定の数字がどちらに入っているかを調べます。この様に繰り返すことでいずれは100を探し当てる事ができます。

＜どれくらいの計算量になるのか＞
n個の配列の中から指定した数値を見つけ出すのに必要な計算回数は、最大でlog₂nとなります。これはステップを繰り返すごとに配列が半分になっていくので、 nが2の何乗で表現できるかが解れば最大計算回数が解るという仕組みです。(例えば8は2の3乗なので、8は3回以上2分割することはできない)

線形探索法は最大n回の計算回数となるので、二分探索法は大幅な計算回数の削減ができます。例えばn=10,000でも二分探索法は14回のステップで見つけ出すことが可能。なお、アルゴリズムの計算量は以下の様にオーダー記法で表現します。