Rubyでアルゴリズムを実装する:Day 3 -二分探索-

最近Ruby書いてて楽しいな。３日目。
2日目はこちら<Rubyでアルゴリズムを実装する:Day 2 -バブルソート->

二分探索とは

ソート済みのデータを半分に絞り込む動作を繰り返して素早く特定のデータを見つけるアルゴリズム。
とても有名で、イメージもしやすい。
というわけで、レッツコーディング

binarySearch.rb

# 二分探索
def binarySearch(num, pat)
  start = 0
  len = num.length - 1
  half = (start + len) / 2
  mid = num[half]

  while mid != pat
    if half < 0 || half > num.length
      half = -1
      break
    elsif pat == mid
      break
    elsif pat < mid
      len = half - 1
    else
      start = half + 1
    end
    half = (start + len) / 2
    mid = num[half]
  end
  half
end

print "格納する数字:"
num = gets.split().map(&:to_i)
print "探す数字："
tar = gets.to_i
binary = binarySearch(num, tar)

if binary >= 0
  puts "#{binary+1}番目に見つかりました。"
else
  puts "数字はありません"
end

出力

格納する数字:1 2 3 4 5 6 7 8 9
探す数字：6
6番目に見つかりました。

コード解説

binarySearch 二分探索を行うメソッドを定義
引数はデータと探索したい値
startとlenにはそれぞれ配列の始点と末端を代入
halfには配列の真ん中の値を示す数を代入
midにデータの中心の値を代入
中央のデータと調べたい値が同値になるまで繰り返す。

もしもhalfが０より下だったり、データの数より大きければhalfを-1で返す。
要はデータがなかったので、falseとして扱う。

中央のデータと調べたい値が同値ならばループ終了

中央のデータが調べたい値より大きければ末端をずらす

中央のデータが調べたい値より小さければ視点をずらす

halfとmidに値を入れなおす

ループ処理が終わればhalfを返す。

データを入力し、何番目にあったのかを出力する。

最後に

探索のイメージはすぐにできたのだが、実装には思いのほか時間がかかった。
始点と末端をうまく動かせずに探索に失敗することがよくあった。

二分探索はsortされたデータ探索しているため、前回実装したバブルソートと組み合わせた方がいいのかもしれない

コード自体に間違いはないと思うが、なんとなく無駄が多いようにも感じる。
というかもっといい方法あるよね

さて、次回は線形探索を実装します(どう考えても順番間違えた。)