【学習ログ】【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のように小数点も含めて表記する必要がある。

本日は以上となります。
最後までお読みくださりありがとうございました。