はじめに
大学2回生？3回生？ぶりに、ソリサーチの実装を行ったので、アウトプット兼ねてまとめます。
バイナリーリサーチとは
バイナリーソートとは、二分探索アルゴリズムのことです。アルゴリズム自体、難しくないので「汚くていいから実装しろ！」と言われればぐにできるものですが、きれいに書こうと思うとなかなか悩みました。
まずは、アルゴリズム全体の流れを以下の画像で見てみます。
参考URL：https://www.codereading.com/algo_and_ds/algo/binary_search.html
任意の値が、配列の真ん中の値よりも小さいか大きいかを判断して、探索対象を狭めていくアルゴリズムです。
具体的手順
- 配列をソートする(ここでは昇順でソートされたとする)
- 配列の中央にある要素を調べる
- 探索
- 中央の要素が目的の値ではなく、目的のデータが中央の値より大きい場合、中央より後半の部分を調べる
- 中央の要素が目的の値ではなく、目的のデータが中央の値より小さい場合、中央より前半の部分を調べる
- 2.に戻る
実際のコード
以上を実際に実装してみます。
sort.rb
def binary_search(array, target)
left = 0
right = array.length - 1
while left <= right
center = (left + right) / 2
if array[center] == target
return center
elsif array[center] < target
left = center + 1
else
right = center - 1
end
end
return -1
end
array=[1,3,5,6,9,10,13,20,26,31]
puts "検索したい数字を入力してください"
target = gets.to_i
result = binary_search(array,target)
if result == -1
puts "#{target}は配列内に存在しません"
else
puts "#{target}は配列の#{result + 1}番目に存在します "
end
これでは長いので、肝心の関数部分にだけ着目します
関数.rb
def binary_search(array, target)
left = 0
right = array.length - 1
while left <= right
center = (left + right) / 2
if array[center] == target
return center
elsif array[center] < target
left = center + 1
else
right = center - 1
end
end
return -1
end
4〜13行目で「中央の要素の定義」を行なって、「検索したい値が中央の要素の左右どちらにあるか」を確かめながら検索を行っています。14行目のreturn -1は何も当てはまるものがないときに、最終的な返り値になります。
ポイントは、配列の方を加工するのではなく中央値として定義している部分を更新して行っているという点です。
仮に、いちいち不要となった部分の配列を削除して新しい配列を用意するようにすると、最終的に有無の判定はできてもどこにあったかが分からなくなります。（インデックスが変わるため）
だからこそ、元の配列を変更しないで、中央値の更新のみで探索をしているのです。
おわりに
今回、学生ぶりにバイナリーソートを実装しました。
この他にも、順番を並び替えるバブルソートだったりと他のアルゴリズムにも触れてみようと思います！