ruby練習問題での備忘録その２

今回のは、バイナリーサーチメソッドを使ってその数値が配列の中の何番目に存在するかを確かめる方法です。

バイナリーサーチとは？

ソートされたリストや配列の中央値を検索し、それを繰り返していく検索アルゴリズム！

コード

今回配列は、

array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

とします。

def binary_search(array, number_of_elements, target)
  left = 0 　//配列の一番初めは０番目から
  right = number_of_elements - 1  // number_of_elementsは、後ほど定義します。この変数は、array.lengthででた配列の数を表しています。lengthででた数値は最初が１ 
  番目から始まるので、-1をしてあげないといけないことに注意が必要。
  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, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

target = gets.to_i　　//知りたい数値を聞く
number_of_elements = array.length　//arrayの配列の数を出す

result = binary_search(array, number_of_elements, target)

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

解説として

今回は、While文を使う事で、繰り返し文を使っています。条件式がTrueの間ずっと行われるのでこれにより答えを導いています。探したい数値が見つかった時に、 returnを使ってWhile文を止めています。 理解に苦しみました...汗