26.1.6.34 二分探索の計算量

二分探索のプログラムでは，検索の範囲を1要素に絞るまで

mid=(low+high)/2;
if(v < a[mid]);
high=mid - 1;
else
low=mid + 1;

という部分を繰り返し実行します．これに対して“頭から探す”方法では，繰り返す部分は

while(a[i]!=v) i=i+1;

ですから，一回の繰り返しあたりの手間は二分検索の方がかなり大きくなります．ところが二分探索では，最初の範囲がたとえ100であっても，

100→50→25→12→6→3→1

と範囲が縮まってゆきますから，わずか六回の繰返ししか必要としません．この繰返し回数を k とすると，

nx(1/2)k=1，

から

2k=n，つまり k=log2n

となります．つまり，二分探索の計算量のオーダは0(log2n) ということになります．

nとlog2nを比較してみましょう．

オーダの比がどんどん大きくなってゆくことがわかるでしょう．実際，単純な探索はn=10程度までしか使用されません．