バイナリーサーチ アウトプット

配列に任意の値が存在するかどうか、そして何番目に存在するのか
という問題です。

array=[1,3,5,6,9,10,13,20,26,31]
arrayの中から検索する数字は6です。

出力結果は、”6は配列の4番目に存在します” です。

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 = 6
number_of_elements = array.length

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

下記が1回目のループです。

def binary_search(array, number_of_elements, target)　#(配列,10(配列の数),6)
  left = 0 #leftは0です。
  right = number_of_elements - 1　　　　# right = 9 (10(配列の数)-1)
  while left <= right　　　　　　　　　　#  0 <= 9
    center = (left + right) / 2　　　　　#（0+9）/2=4(配列の番号)
    if array[center] == target    　　　#9(配列の4番目)==6
      return center     　　　　　　　　
    elsif array[center] < target　　　　# 9 < 6
      left = center + 1　
    else
      right = center - 1　　　　　　　　　#4(center)-1=3
     end
  end
  return -1                        
end

array=[1,3,5,6,9,10,13,20,26,31]  #配列です。添字は0からカウント

puts "検索したい数字を入力してください"
target = 6(gets.to_i)              #検索する数値
number_of_elements = array.length    #配列の数=10

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

下記が2回目のループです。

def binary_search(array, number_of_elements, target)
  left = 0
  right = number_of_elements - 1
  while left <= right　　　　　　　　　#0<=3(1回目ループのright)
    center = (left + right) / 2　　#（0+3）/2=1
    if array[center] == target     #3==6
      return center
    elsif array[center] < target   #3<6
      left = center + 1            #1+1=2
    else
      right = center - 1
    end
  end
  return -1 
end

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

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

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

下記が3回目のループです。

def binary_search(array, number_of_elements, target)　
  left = 0
  right = number_of_elements - 1
  while left <= right　　　　　　　　　　　#2(2回目のループleft)<=3
    center = (left + right) / 2      #(2+3)/2=1
    if array[center] == target        #3==6
      return center                    
    elsif array[center] < target      #3<6
      left = center + 1                #2+1=3
    else
      right = center - 1
    end
  end
  return -1 
end

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

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

result = binary_search(array, number_of_elements, target)
result += 1     #result（array）を1からカウントに変更　
if result == -1                         
  puts "#{target}は配列内に存在しません"
else
  puts "#{target}は配列の#{result}番目に存在します "　
end

下記が4回目のループです。計算結果が出力されます。

def binary_search(array, number_of_elements, target)　
  left = 0
  right = number_of_elements - 1
  while left <= right　　　　　　　　　　　#3(3回目のループleft)<=3
    center = (left + right) / 2      #(3+3)/2=3
    if array[center] == target        #6==6
      return center                    # center=3
    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 = 6
number_of_elements = array.length #配列の数=10

result = binary_search(array, number_of_elements, target) # binary_searchの計算結果=3
result += 1     #result（array）を1からカウントに変更　3 → 4
if result == -1                          #3 == -1
  puts "#{target}は配列内に存在しません"
else
  puts "#{target}は配列の#{result}番目に存在します "　#target=6 result=4
end