仕事をやり遂げるために必要な時間を見立てることが出来たら,
前回は,
計算量:バイナリサーチの場合O (log2(n))
バイナリサーチ
- [Step 1]
図75.
2の①のように, 5個の整数を格納した配列 vals
から値「5」 を格納した位置(添え字の値)を検索する場合 ( target=5
)を紹介します。 先ず検索範囲を設定します。最初ですから左端は配列の先頭要素ですので,
変数 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=log2(x) のグラフとy=x のグラフを並べて描くと,
x が大きくなるほどバイナリサーチが有効なことがよく分かります。 - ※1)
- binary search
- ※2)
- median