バイナリサーチ

12月 16th, 2007 admin Posted in Ruby, アルゴリズムとデータ構造 |

今回はバイナリサーチ（二分探索です。サーチといえばバイナリサーチというぐらい有名です。
ランダムに並んだ配列データをサーチする場合において、これ以上速い方法はないそうです。

考え方は難しくないし、日常生活でも自然に使っていたりします。

アルゴリズム

データをソートする
まず真ん中の値をチェックして、それより大きいか小さいかを判断する。
大きければ、小さかったほうの探索はもうしない。次に大きいほうの配列の真ん中の値をチェック・・・と半分＞半分＞半分と絞り込んでいく方法

コード

#バイナリサーチ
require 'pp'
before = Time.now
t = Time.now
srand(t.sec ^ t.usec ^ Process.pid)

#探索する要素数
Num = 10

def binarySearch(target,a)
	left = 0
	right = a.size - 1

	while(left < right)
		mid = (left + right) / 2

		if a[mid] == target
			return mid
		end

		if(a[mid] < target)
			left = mid + 1
		else
			right = mid
		end
	end

	if a[left] == target
		return left
	end

	return nil
end

#ランダムな値の入った配列を作成
a = Array.new
Num.times{|i|
	a.push rand(Num)
}

#探す数値
target = rand(Num)

#配列をソート
a.sort!

#出力
p "serch:" + target.to_s
pp a

#p binarySearch(target,a);

#処理時間
p Time.now - before

ふつうのRuby

RAAにSatoru Takabayashiさんによるbserachというのが登録されています。

まとめ

二分探索という言葉はわかりやすけど、バイナリってのがわかりにくい。バイナリって二分という意味もあるんだろうか？調べてみたけど２進って意味はあるみたいだけど、ちょっと違う気もする･･･けど間違ってるのはどうせ僕のほうなので誰か賢い人に聞いてみようと思う。

※このシリーズは私がRubyでアルゴリズムとデータ構造を基礎から学ぶ記録です。全体の目次はこちらへ。