Rubyの練習問題 ~バイナリーサーチ~

問題.1

配列に任意の値が存在するかどうか、検索するコードを作成しましょう。
任意の値が配列内に存在しない場合は値は配列内に存在しませんと表示され、
存在する場合は、配列の何番目にあるかを表示してください。

配列　array=[1,3,5,6,9,10,13,20,26,31]

検索はバイナリーサーチ（２分割検索）を使用して行います。

[自分の解答]

def binary_search(array, right, target)
  left = 0
  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 "検索したい数字を入力してください"
num = gets.to_i
number_of_elements = array.count

result = binary_search(array, number_of_elements, num)

if result ==  -1
  puts "#{num}は存在しない"
else
  puts "#{num}は#{result + 1}番目"
end

正直前回より理解度は増していない。
今回解いても理解できなかったので補足を見ながら解いた。
この手の問題は、メソッドを先に作るより、先にそれ以外を記述してからの方が良い。
この場合はbinary_search(array, number_of_elements, num)の部分まで。
そして、配列の要素数の真ん中の値をcenterとして配列[center]から左にずれるか右にずれるかで検証する。
ここではrightの値を要素数の値にしている。右にずれて検証する場合は、この値を-1としていく。
逆に左にずれる場合は、leftの変数の値を+1としていき、最終的に要素数の半分の値と同じになったらwhileを終了する。

例えば、31を検証したいとする。
centerはここでは要素数の半分の値となるので、5。つまりarray[5]となる。
当然31とは一致しないし、31より小さいのでleftに1加算される。
次のcenterの値は(left(=center +  1) + 10) / 2 でarray[8]。
ここでも一致しないし31より小さい。
よって、centerに+1された値がleftに入り、centerの値は 9 + 10 /2 で切り捨てで9となる。
ここでarray[9] = 31となるので、一致。返り値がcenterで9となる。
この値を変数resultに代入。
値が存在しない場合、 返り値は-1で返ってくるようになっているので、その場合は存在しないと出力する。
存在すれば、何番目にあるかを出力する。
ただし配列は0から数えることに注意すること。

検証する値が例えば1の場合は、leftの値は変わらずright(=要素数の値)が変動していく。