Rubyでバイナリーリサーチ（二分探索）の実装

※2022年から技術系の記事は個人ブログに投稿しております。ぜひこちらもご覧ください→yamaday0u Blog

スクールのドリルでだいぶ苦戦したのでバイナリーリサーチの実装方法について整理します。

def binary_search(array, right, target)
  left = 0
  while left <= right
    # 要素の左端と右端を足して二分した値をcenterへ代入
    center = (left + right) / 2
    if array[center] == target
      # centerで指定した位置の配列の数字と検索したい数字が一致すれば
      # centerを返す
      return center
    elsif array[center] < target
      # centerで指定した位置の配列の数字より検索したい数字が大きい場合、
      # centerに１を足した数値を左端の位置を表すleftに代入
      left = center + 1
    else
      # centerで指定した位置の配列の数字より検索したい数字が大きい場合、
      # centerから１を引いた数値を右端の位置を表すrightに代入
      right = center - 1
    end
  end
  # 検索したい数字が配列の中の数字と一致しなかった場合、-1を返す
  return -1
end

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

puts "検索したい数字を入力してください"
target = gets.to_i

result = binary_search(array, number_of_elements, target)

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

たとえば26を検索したい場合、以下の動きをします。

# whileの1回目のループ
center = ( 0 + 9 ) / 2 = 4 # 計算結果の小数点以下は切り捨てられる
array[4] = 9 < 26
left = 4 + 1 = 5

# whileの2回目のループ
center = ( 4 + 9 ) / 2 = 6
array[6] = 13 < 26
left = 6 + 1 = 7

# whileの3回目のループ
center = ( 6 + 9 ) / 2 = 7
array[7] = 20 < 26
left = 7 + 1 = 8

# whileの4回目のループ
center = ( 8 + 9 ) / 2 = 8
array[8] = 26 == 26
return 8

# 実行結果=>"26は配列の８番目に存在します。"