仕事をやり遂げるために必要な時間を見立てることが出来たら，次はその時間をいかに短縮するかを考えます。同じ仕事が短時間で出来るなら，それにこしたことはありません。余った時間で間違いがないかどうかの確認や，より品質を高めることが出来ます。

前回は，計算量O (n )のアルゴリズムの例としてリニアサーチを取り上げました。要素の数nの大きさに比例して，最悪検索時間が長くなります。今回は，リニアサーチよりも高速なバイナリサーチの計算量を求め，実際にコードを動かして速さの違いを実感しましょう。本当に同じ仕事を，より短い時間で実行できるのでしょうか。

計算量：バイナリサーチの場合O (log₂(n))

バイナリサーチ（※1）とは，データの真ん中の値，すなわち中央値（※2）を「とりあえず」チェックする方法です。データは整列済みで，小さい値から大きい値の順に並んでいます。目的の値が中央値だろう，と当たりを付けるのです。もちろん，一発で目的の値になることは少ないでしょう。でも，この「当たりを付ける」ということがとても有効なんです。図75.2を用いて解説します。

[Step 1]

図75.2の①のように，5個の整数を格納した配列valsから値「5」を格納した位置(添え字の値)を検索する場合（target=5）を紹介します。

図75.2　バイナリサーチとは

先ず検索範囲を設定します。最初ですから左端は配列の先頭要素ですので，変数left=0，右端は配列の末尾要素ですから変数right=vals.length-1=4となります。中央値の位置は(left+right)/2=2です。

もし，中央値が目的の値ならば，めでたく検索は終了です。しかし，違っていれば，中央値と目的の値の大小を比較します。もし，中央値よりも目的の値が小さければ，中央値以降のデータは捨ててしまいます。今回は，中央値より目的の値が大きいので，中央値より前のデータを捨てます。

[Step 2]

図の②のように，Step1の操作によって，注目する配列の範囲はn/2 になりました。話を簡単にするために，nの偶奇は考えません。実際にコードを組む際には，n/2 を整数変数の除算として取り扱えば，小数部分が発生せず，都合良く範囲が決まります。

新しい配列の中央の値と目的の値を比較します。等しければ検索は終了。

等しくなければ大小を比較します。中央値よりも目的の値が大きいので，現在注目しているデータ以前を捨ててしまいます。

[Step 3]

図の③のように，Step2の操作によって，残った配列のサイズは(n/2)/2になりました。今回の場合では残りのデータは1つだけになりました。ここで探す値target=5と配列の値vals[4]=5が等しいので，めでたく検索は成功し終了です。もし，vals[4]の値が5でなければ，探す値は配列内に存在しなかった，ということで，検索は失敗し終了します。検索に失敗した場合には，－1などの，配列の添え字としてあり得ない値を返して，検索に失敗したことを表明しましょう。

[Step a，最悪の場合]

最悪の場合，配列のサイズが1になるまでこのアルゴリズムが実行されます。繰り返しの回数aは次のような式で表されます。

バイナリサーチの計算量

O (log2(n))

y=log₂(x) のグラフとy=x のグラフを並べて描くと，x が大きくなるほどバイナリサーチが有効なことがよく分かります。

図75.3　y=xとy=log₂xのグラフ

※1）

binary search

※2）

median