はじめに
ITエンジニアなら、基本的なアルゴリズムは知っておきたいよねとか言われても、一つも知らなかった。
まず、なぜ知って起きたいほど重要なのかをハラ落ちさせたかったので色々調べてみた。
この記事に、アルゴリズムが大事だという２つ理由がありました。
速く基本的なアルゴリズムが正しく組める人は、他のコードを書かせてもバグを入れにくいうえ、作業が速い。もちろん、アルゴリズムを組むのが遅くても、バグの少ないコードを書く人は沢山いる。でも、アルゴリズムを速く正確に組める人は概して他のコードを書かせても素早いし、バグを入れにくい。雇う側からすれば、バグが少なく開発スピードが速いに越したことはない。
もう一つは
効率的なアルゴリズムはコスト削減につながる。当然の話だが、同じ機能だったら出来る限り少ないリソースでできた方が、コストが減って儲けにつながる。ソフトウェアもビジネスなので、コストが低いに越したことはない。そこで様々なソフトウェアの最適化がされるのだが、多くの場合、もっとも大幅にリソース使用量を減らせるのが、より効率的なアルゴリズムを使うことだ。裏を返せば、効率的なアルゴリズムがちゃちゃっと組めないエンジニアは、コードを書く度に、それだけ会社に損をさせていることになる。
アルゴリズムを勉強すると、応用力が効くし、コードの安全性も増すことができるということだろう。よし、ハラ落ち。
次に、本屋で簡単そうなアルゴリズムの本を買ったので、それを今勉強中のRubyで書いてみようというのをやって行こうかと思います。
今回は...
二分探索法
教科書はp102にあります。
二分探索法（バイナリサーチ）は、探索アルゴリズムの一種です。探索アルゴリズムとは、目的のデータを探し出すアルゴリズムのことです。検索エンジンもこのアルゴリズムを利用しているみたいです。
二分探索法（バイナリサーチ）とは
配列が must be sorted （ソート済み）データを、半分割しながらデータを探すアルゴリズムです。
ポイントは2つです
- あらかじめ昇順（小さい順）か降順（大きい順）か整列されているデータが対象
- 探索する範囲を半分に絞りながら探索をする
例を見てみましょう。
二分探索法（バイナリサーチ）のアルゴリズムの例
- 「13」という文字を探したいとします
- まず、中間点を探索します
- 「20」なので、目的の数字は左側にあるとわかります
- なので、右側は対象外とします
- 対象内の中間点を探索します
- 「4」なので、目的の数字は右側にあるとわかります
- なので、左側は対象外とします
- 対象内の中間点を探索します
- 「4」なので、目的の数字は右側にあるとわかります
- なので、左側は対象外とします
- 対象内が偶数の場合は中間点が２つあると思います
- その時は、右側か、左側かどちらかを選ぶといいです
- ちなみに、整数同士の商の小数点は切り捨てられるので左側を選んでいることになります
- 「5」なので、目的の数字は右側にあるとわかります
- なので、左側は対象外とします
これで、目的の値が探索できました。
目的の値がない場合
目的の値がない場合は、どんな場合でしょうか？
- 昇順の配列の場合
- 中間点（center）が目的の数値よりも少ない時、次のデータの探索範囲は右側になります
- その際
- 始点は centerの値 + 1 になり
- 終点は 配列の一番後ろの値 になります
- その際
- 中間点が目的の数値よりも大きい時、次のデータの探索範囲は左になります
- その際、
- 始点は 配列の一番前の値 になり
- 終点は centerの値 - 1 になります
- その際、
- 中間点（center）が目的の数値よりも少ない時、次のデータの探索範囲は右側になります
このアルゴリズムの場合、目的の値がない場合、始点 ≦ 終点 が false になります。
その時、目的の値がないとわかります。
実際に試してみるとわかります。
処理の流れ
教科書と同じよう内容の配列を用意します。
| 配列の要素 | 値 |
|---|---|
| array [0] | 11 |
| array [1] | 13 |
| array [2] | 17 |
| array [3] | 19 |
| array [4] | 23 |
| array [5] | 29 |
| array [6] | 31 |
1週目
- target = 17
- head = 0
- array[head] = 11
- tail = 6
- array[tail] = 31
- center = 3
- array[center] = 19
target（17） < array[center]（19） なので、次の探索範囲は center よりも小さい範囲に限定された
範囲の 始点と終点は下記
- head = 0
- tail = center（3） - 1
2週目
- target = 17
- head = 0
- array[head] = 11
- tail = 2
- array[tail] = 17
- center = 1
- array[center] = 13
target（17） > array[center]（13） なので、次の探索範囲は center よりも大きい範囲に限定された
範囲の 始点と終点は下記
- head = center（1） + 1
- tail = 2
3週目
- target = 17
- head = 2
- array[head] = 17
- tail = 2
- array[tail] = 17
- center = 2
- array[center] = 17
target（17） = array[center]（17） 探索完了
それでは、このアルゴリズム通りにRubyでコードを書いていきます。
Rubyで二分探索法（バイナリサーチ）を書いてみた
array = [ 11, 13, 17, 19, 23, 29, 31 ]
def binary_search(array, target)
head = 0
tail = array.count - 1
while head <= tail
center = (head + tail) / 2
if array[center] == target
return "index = #{center}"
elsif array[center] < target
head = center + 1
else
tail = center - 1
end
end
return "index is nothing"
end
# 探したい値
target = 17
# 二分探索法（バイナリサーチ）の実行
p binary_search(array, target)
実行結果
ruby section_5.rb
=> "index = 2"
以上です！イケてないコードであればご指摘ください。
レポジトリ
参考図書
伊藤静香. アルゴリズムを、はじめよう. 第5章. インプレス, 2012, p. 102-115.