Ruby バイナリーサーチ

バイナリーサーチとは

ソート済みのリストや配列に入ったデータ（同一の値はないものとする）に対する検索を行うときに用いられる手法です。まず、中央の値を確認し、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断します。それを繰り返し、片側には存在しないことを確かめながら検索していく方法です。

#13の位置を知りたい
array = [2, 3, 5, 6, 8, 10, 11, 13, 16]
#添字　　　   0, 1, 2, 3, 4,  5,  6,  7,  8
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　↓
        [10, 11, 13, 16]
#添字      5,  6,  7,  8
              ↓
          [13, 16]
#添字        7,  8

上記のような配列があったとして「13」を検索したいとしたら、まず配列の中央の要素を求める。4番目が中央なので「8」。ターゲットの「13」は「8」より大きいとなるので次は「10」を左端として検索する。

次に6番目の要素「11」が配列の中央。ターゲットの「13」は「11」より大きいので「13」を左端として検索。

次に７番目の要素「13」が中央になり、ターゲット「13」は「13」と等しい。

一度の処理で選択肢が半分になり、処理速度の向上が期待できるということがある。

問題

以下の配列に任意の値が存在するかどうか、そして何番目に存在するのか、検索するコードを作成しましょう。
添字が0の要素、つまり以下の配列における「1」は「配列の0番目に存在する」と表現します。

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

任意の値が配列内に存在しない場合は、「値は配列内に存在しません」と表示し、
存在する場合は、配列の何番目にあるかを表示してください。

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

解答

qiita.rb

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 "検索したい数字を入力してください"
target = gets.to_i
number_of_elements = array.length

result = binary_search(array, number_of_elements, target)

if result == -1
  puts "#{target}は配列内に存在しません"
else
  puts "#{target}は配列の#{result}番目に存在します "
end

ターゲットが5だとしたら、以下のような処理になる

# target = 5 , right = 10, left = 0, center = 5, array[center] = 10
# right = 4, left = 0, center = 2, target = 5, array[center] = 5

左0番目、右10番目、右と左を足して2で割ってセンターは5番目、5番目の要素は10。
要素10はターゲット5と等しい→False,ターゲット5は要素10より大きい→False
ならば5番目からマイナス1で5番目以降は検索の対象から外した状態でまた中央値をみる。
右4番目、左0番目、右と左を足して2で割ってセンターは2番目,2番目の要素は5。
となり、ターゲット5は配列の5番目に存在する。

というふうに言語化してみた。間違いなどあったりもっとこうした方がいいとかありましたらご指摘ください。
以上でした。