以下の配列に任意の値が存在するかどうか、そして何番目に存在するのか、検索するコードを作成しましょう。
添字が0の要素、つまり以下の配列における「1」は「配列の0番目に存在する」と表現します。
array=[1,3,5,6,9,10,13,20,26,31]
任意の値が配列内に存在しない場合は、「値は配列内に存在しません」と表示し、
存在する場合は、配列の何番目にあるかを表示してください。
検索はバイナリーサーチ(2分割検索)を使用して行います。
答え
def binary_search(array, number_of_elements, target)
left = 0
right = number_of_elements - 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,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
前半で中央要素の定義と検索したい要素が右か左かにあるかを確かめながら検索をしています
何も当てはまらないときは return -1 を返します。
例題で31を代入していた物があったのでそちらも紹介します。
#1回目のループ
leftは0
rightは9
5行目:centerは4(小数点以下は切り捨てされます)
6行目:if array[center]==31
#=>array[center]は9なのでfalse
8行目:elsif array[center] < target
#=>array[center]は9であり、31より小さいのでtrue
11行目:leftはcenterに+1して5となる
#2回目のループ
leftは5
rightは9
5行目:centerは7
6行目:if array[center]==31
#=>array[center]は20なのでfalse
8行目:elsif array[center] < target
#=>array[center]は20であり、31より小さいのでtrue
11行目:leftはcenterに+1して8となる
#3回目のループ
leftは8
rightは9
5行目:centerは8
6行目:if array[center]==31
#=>array[center]は26なのでfalse
8行目:elsif array[center] < target
#=>array[center]は26であり、31より小さいのでtrue
11行目:leftはcenterに+1して9となる
#4回目のループ
leftは9
rightは9
5行目:centerは9
6行目:if array[center]==31
#=>array[center]は31なのでtrue
となります。
この問題の感想ですがスクール卒業時期が今月なのですがこの問題は初心者向けなのでしょうか?
かなり難しく感じまだ自分の実力では解けませんでした。
早く一人前のエンジニアになりたいと思う日々です。