[Ruby]バイナリーサーチとは

ruby の問題を解いていたところ
躓きましたので備忘録として残します。

バイナリーサーチとは？

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

・・・理屈ではわかります。ただ、それをコードでどのように記述すればよいのか？

回答

※配列の上限である32以上の値による検索は想定しないものとする
※検索はバイナリーサーチ（2分割検索）を使用して行う

１回目のループ
def binary_search(array, right, target)　 #=> right=配列の数、target=26
  left = 0
  while left <= right
    center = (left + right) / 2
    if array[center] == target　#=> array[5]=10 なのでここには当てはまらない
      return center
    elsif array[center] < target　#=> 10<26　なのでここの処理が実行される
      left = center + 1　　#=> left=6　となり、２回目のループに入る
    else
      right = center - 1
    end
  end
  return -1 #=>何も当てはまらないときの返り値
end

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

target = 26
number_of_elements = array.length #=> 配列の数

result = binary_search(array, number_of_elements, target)

２回目のループ
def binary_search(array, right, target)　 #=> right=配列の数、target=26
  left = 0　　#=> こちらに１回目の数字６が入ります。
  while left <= right
    center = (left + right) / 2 #=> （6+10）/2 = 8
    if array[center] == target　#=> array[8]=26 なのでここの処理が実行されます
      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]

target = 26
number_of_elements = array.length #=> 配列の数

result = binary_search(array, number_of_elements, target)

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

よって、「26は配列の８番目に存在します」が表示されます。
※配列は０からスタートします。

returnにたどりつくまで、繰り返します。