はじめに
この記事では2分探索についてRubyで解説していきます。
2分探索とは
2分探索は要素がキーのの昇順や降順に整列(ソート)している配列から効率よく探索を行うアルゴリズムです。
2分探索はバイナリーサーチとも呼びます。
実装例
2分探索をRubyで実装していきます。
binary_search.rb
#配列aの先頭number個からtargetと一致する要素を2分探索(探索が失敗したら-1を返す）
def binary_search(a , number, target )
first_index = 0 #探索範囲先頭の要素
last_index = number - 1 #探索範囲末尾の要素
begin
center_index = (first_index + last_index) / 2 #中央の要素
if a[center_index] == target
return center_index #探索成功
elsif a[center_index] < target
first_index = center_index + 1 #探索範囲を後半に絞り込む
else
last_index = center_index - 1 #探索範囲を前半に絞り込む
end
end while first_index <= last_index
-1 #探索失敗
end
puts "要素数を入力してください。"
print "要素数："
number = gets.to_i
a = []
puts "昇順に入力してください。"
print "a[0]：" #先頭の要素を先に読み込む
a[0] = gets.to_i
#昇順に入力する
(1..number - 1).each {|i|
print "a[#{i}]："
a[i] = gets.to_i
redo if a[i] <= a[i - 1] #1つ前の要素より同じか小さければ再入力
}
puts "探す値を入力してください。"
target = gets.to_i
result = binary_search(a, number, target)
if result == -1
puts "その値は存在しません。"
else
puts "その値はa[#{result}]にあります。"
end
コードの解説
では上記のコードの解説をしていきます。
1.昇順の配列aを用意する
まず最初に昇順で数字が並んでいる配列aがを用意します。
ここでは、配列は標準入力を利用して用意しています。
2.配列の中央にある要素を調べる。
次にbinary_searchメソッドで配列の中央にある要素を調べます。
先頭の要素(first_index)と末尾の要素(last_index)を足して2割ったものが中央にある要素(center_index)となります。
3.探索する
では、いよいよ探索を開始します。
中央の要素が目的の値の場合
中央の要素(center_index)が目的の値(target)の場合はそこで探索が終了します。
目的の要素が中央の要素より小さい場合
探索範囲を配列aの後半に絞り込み探索を続けます。
目的の要素が中央の要素より大きい場合
探索範囲を配列aの前半に絞り込み探索を続けます。
探索が失敗する場合
探索を繰り返していき先頭の要素(first_index)が末尾の要素(last_index)以上になってしまった場合、その時点で配列aのなかに目的の要素が無いということが分かるので探索失敗です。
以上でコードの解説を終了します。
最後に
以上で2分探索についての解説を終了します。
何か間違っていることがあったらご指摘ください
参考
以下の書籍を参考にしました。