【学習ログ】【Ruby】二分探索法(バイナリサーチ)プログラム

※このページは過去に自分がRubyの勉強をしたときの学習ログです。誰かの参考になれば幸いです。

二分探索法(バイナリサーチ)をRubyで作成してみた

いきなり完成コード

# 二分探索法(バイナリサーチ)
def binary_search(numbers,target_number)
  head = 0
  tail = numbers.length-1
  

  while head <= tail
  center = ((head + tail) / 2.0).round
  
    if numbers[center] == target_number
      return center
  
    elsif numbers[center] < target_number
      head = center +1

    else
      tail = center -1
    end
  end
return "None"
end


numbers = [1,3,5,11,12,13,17,22,25,28,30]

puts('配列numbersから探したい数字を入力してください')

target_number = gets.to_i

puts binary_search(numbers,target_number)

実行結果 →
配列numbersから探したい数字を入力してください
30
10

配列numbersから探したい数字を入力してください
40
None

解説(我流です)

バイナリサーチとは検索アルゴリズムの1つで、例えば5と言う数字を探したい時にまず配列の中央の値に注目し、
その数字と探したい数字を比較し、探索する範囲を2つに分けて、半分に絞込みながら探索をする方法のこと。

リニアサーチ同様、解説できるほど理解が追いついていないが、roundメソッドについては理解できた。
配列の中央を割り出すのに( 配列の先頭の添字 + 配列の末尾の添字 ) / 2.0という方法を用いるが、
配列の個数が奇数だった場合に2で割り切れず添字[3.5]などのインデックスになってしまう。
添字[3.5]などのインデックスは存在しないため、これを四捨五入するのにRubyのメソッドであるroundを使う。
ただしroundメソッドで扱う数字は2.0のように小数点も含めて表記する必要がある。

本日は以上となります。

最後までお読みくださりありがとうございました。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

コメントする