hibikousinnkibouのブログ

駆け出しプログラマーによる足跡ブログ

バイナリーサーチを利用した、配列の何番目に存在するか、又は存在しないことを確認する問題

以下の配列において、

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

任意の値が配列内に存在しない場合は、「値は配列内に存在しません」と表示し、存在する場合は、配列の何番目にあるかを表示してください。

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

 

私の回答は、

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

def binary_search(array,target)
head = 0
tail = array.length
while head <= tail
center = ((head + tail) / 2).ceil
if array[center] == target
return "配列の#{center+1}番目に存在する"
elsif array[center] < target
head = center + 1
else
tail = center - 1
end
end
return "値は配列内に存在しません"
end
puts "検索したい数字を入力してください"
target = gets.to_i

puts binary_search(array,target)

で正解を出せた。

整数同士の計算なので整数を返すはずなので不要と考えたが、念の為切上げの .ceil を記述。

"配列の#{center+1}番目に存在する"

の部分が理解が出来なかったので今後の課題としたい。

 

模範回答は、

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
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

と right をいつどこで定義したのか分からないがこういった内容であった。

コードに対する理解を深めなければいけないが、バイナリーサーチについては概ね理解した。