rubyの検索問題 バイナリーリサーチ

問題

• 以下の配列に任意の値が存在するかどうか、そして何番目に存在するのか、検索するコードを作成する。

• 添字が0の要素、つまり以下の配列における「1」は「配列の0番目に存在する」と表現します。

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

• 任意の値が配列内に存在しない場合は、「値は配列内に存在しません」と出力する。
• 存在する場合は、配列の何番目に存在するのか表示する。

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

補足(バイナリーリサーチとは？)

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

解答

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する。
target(検索したい値)が中央の値より小さい場合は、右から-1する。

return -1の記述は検索したい値が配列内に存在しなかった場合の戻り値として記述している。

その結果を

result = binary_search(array, number_of_elements, target)

の変数resultに代入している。

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

上記で-1だった時、つまり配列内に存在しなかった場合と
配列内に存在した場合とに条件分岐している。

最後に

バイナリーリサーチの概念は非常に難渋したので、
備忘録として残しておきました。