[計算量をざっくり理解] 2分探索の計算量

2分探索

二分探索（にぶんたんさく、英: binary search、BS）やバイナリサーチとは、ソート済み配列に対する探索アルゴリズムの一つ。

出典: フリー百科事典『ウィキペディア（Wikipedia）』

ソートされている配列の探索は、線形探索ではなく2分探索を使うことで、計算量を減らすことができます。

探索の時に、最初から値を見るのではなく、まずは中央の値を見て、目標との大小関係により、目標が中央の値の右にあるか、左にあるかを判断することで、存在しないほうの半分のデータを省いていきます。

例えば、以下のような配列を考えます。

この配列で「3」を2分探索してみます。

まずは、中心の「13」を見ます。目標の「3」は「13」より小さいので存在するならば左半分に存在するはずです。よって、次は以下のような配列を2分探索します。

これを、目標が見つかるか、配列の個数が1個になるまで続けます。

2分探索の計算量を考えます。

N個の配列を考えた時、一度の探索で探索範囲が半分になり、配列の個数が1になるまで探索を続けるので、探索回数を\(x\)と置いて、以下のように立式して解きます。

\( 1 = \displaystyle \frac { N } { 2^x } \)

\( 2^x = N \)

\( \log 2^x = \log N \)

\( x = \log N \)

よって、2分探索は、\( O ( \log N ) \) の対数 Logarithmic の実行時間となります。

これは、例えば、「配列の個数が4倍になったときは2倍の実行時間が必要になる」ことを意味しています。

線形探索の場合は 「配列の個数が4倍になったときは4倍の実行時間が必要になる」ことと比較すると、2分探索の計算量は少なくなります。