Help us understand the problem. What is going on with this article?

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

最近Ruby書いてて楽しいな。3日目。
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が0より下だったり、データの数より大きければhalfを-1で返す。
要はデータがなかったので、falseとして扱う。

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

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

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

halfとmidに値を入れなおす

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

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

最後に

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

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

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

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

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away