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

学習したことのアウトプットとして

バイナリーサーチを用いた問題、理屈はわかるが、実際自分でコードを描こうとすると脳が混乱…。
ので、自分なりに整理してみようかと。

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

例)ある配列にある１３の位置を知りたい

2	3	5	6	8	10	11	13	16
４番目の"8"が要素の中央。１３は８より大きいので、次は"10"を左端として検索
↓

10	11	13	16
6番目の"11"が要素の中央。１３は１１より大きので、次は"13"を左端として検索
↓

13	16
7番目の"13"が要素の中央。検索したい１３と合致
↓
「１３は配列の７番目」

という風な感じ。理屈自体は難しいものではないかと。

要素数が偶数の場合、「中央」は数が少ない方（左側）が優先されるのか？
詳しい人がいらっしゃればコメントいただけると幸いです。

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

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

任意の値が配列内に存在しない場合は、「値は配列内に存在しません」と表示し、
存在する場合は、配列の何番目にあるかを表示してください。
※配列の上限である32以上の値による検索は想定しないものとする。

###模範解答

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

###解説

１〜１４行目

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

検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索を行う処理を行ってる。

たとえば、targetとして"２０"を入力した場合を考えてみる

1回目のループ

def binary_search(array, right, target) #(配列,１０（配列の数）,２０）
  left = 0
  while left <= right #0 <= 10 はtureで処理が実行される
    center = (left + right) / 2 #要素の中央　　(0+10) / 2 = 5
    if array[center] == target #array[5]は"10"でfalseなので、この処理はされない
      return center
    elsif array[center] < target #trueなのでこの処理が実行される
      left = center + 1 #２回目のループではleft=6（配列の中央から右側に検索範囲を絞る）
    else
      right = center - 1
    end
  end
  return -1 
end

2回目のループ

def binary_search(array, right, target) #(配列,１０（配列の数）,２０）
  left = 6 #1回目のループより
  while left <= right #６ <= 10 はtureで処理が実行される
    center = (left + right) / 2 #要素の中央　　(６+10) / 2 = ８
    if array[center] == target #array[8]は"26"でfalseなので、この処理はされない
      return center
    elsif array[center] < target #26 < 20 でfalse
      left = center + 1
    else
      right = center - 1 #ここの処理がされる。３回目のループではright=9（１回目で絞った配列からさらに中央から左側に検索範囲を絞る）
    end
  end
  return -1 
end

３回目のループ

def binary_search(array, right, target) #(配列,１０（配列の数）,２０）
  left = 6 #1回目のループより
  while left <= right #６ <= ９（２回目のループより) はtureで処理が実行される
    center = (left + right) / 2 #要素の中央　　(６+9) / 2 = 7
    if array[center] == target #array[7]は"20"でture
      return center   #7　が返り値となる
    elsif array[center] < target 
      left = center + 1
    else
      right = center - 1 
    end
  end
  return -1 
end

13行目のreturn -1は何も当てはまるときがないときに、最終的な返り値になる。

返り値を元に条件分岐を利用して出力内容を設定する。

記事を書いて、少し自分の中でも整理できたのでよかった！