本日の基礎練習問題(22/3/19)

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

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

任意の値が配列内に存在しない場合は、「値は配列内に存在しません」と表示し、
存在する場合は、配列の何番目にあるかを表示してください。
※配列の上限である32以上の値による検索は想定しないものとします。
検索はバイナリーサーチ（2分割検索）を使用して行います。

ヒント
まず.lengthメソッドを使用して配列の要素数を取得し、変数number_of_elementsとします。
binary_searchメソッド内で配列の要素数を半分にしたものを変数centerとしましょう。
while文を使用して、当てはまるまで計算を繰り返します。

出力例：

検索したい数字を入力してください
5
5は配列の2番目に存在します 

検索したい数字を入力してください
7
7は配列内に存在しません

私の回答

　# 処理内容書けずタイムアップ

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

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

模範回答

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

模範解説

1〜14行目で中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索を行う処理を行っています。13行目のreturn -1は何も当てはまるときがないときに、最終的な返り値になります。

たとえば、targetとして31を入力した場合を考えてみましょう。そうすると2〜12行目で以下のように処理が進みます。

#1回目のループ
left=0
right=10
center=5
array[center]=10

#2回目のループ
left=6
right=10
center=8
array[center]=26

#3回目のループ
left=9
right=10
center=9
array[center]=31

そして6行目のreturn centerによって返り値が9となり、24〜28行目の処理で31は配列の9番目に存在しますと出力されます。

感じたこと

ネットで調べながら解いたが時間をかけすぎて処理内容を書けなかった。
かなり難しいと感じた。正直答えを見ても変数rightとarray[center]の動きがいまいちよくわからない。
1から整理して理解できるようにしたい。
またバイナリーサーチは聞いたことがなかったので学習し使用できるようにしたい。
※実際に開発現場で使用しているかはわからないが‥‥

プログラミング未経験なので初見ではなかなか厳しい問題が多くなってきましたが
逆に吸収できることが多いので良い意味で捉え日々成長していきたい。

まだまだruby初心者ですのでアドバイスやご指摘等ございましたらぜひお願いします！！！

以上