バイナリサーチを使った、配列における任意の検索方法

【概要】

1.結論

2.バイナリサーチとは何か

3.どのようにコーディングするか

4.ここから学んだこと（エラーの時に使用）

1.結論

lengthメソッドとwhile文、if文を組み合わせて使う！


2.バイナリサーチとは何か

配列に入ったデータ等（同じ値は入っていないものとします）に対して行う検索方法です。内容としては、中央の値を確認し、そこから左右との大小関係を比較し順々に探していく検索方法です！


3.どのようにコーディングするか

def binary_search(array, number_factors, value)
  min_factor = 0
  max_factor = number_factors - 1 #---❷
  while min_factor <= max_factor do　#---❸
    center_factor = (min_factor + max_factor) / 2　#---❹
    if array[center_factor] == value
      return center_factor
    elsif array[center_factor] < value
      min_factor = center_factor + 1
    else
      max_factor = center_factor - 1 #---❺
    end
  end
  return -1　#---❻
end

array=[1,2,3,6,7,10,11,23,25,31]

puts "お探しの数字は何番でしょうか？"
value = gets.to_i
number_factors = array.length　#---❶

result = binary_search(array, number_factors, value)

if result == -1　#---❼
  puts "#{value}は現在登録されておりません。"
else
  puts "#{value}は#{result}番目です。"
end

❶：まずarrayの配列の要素を数えます。バイナリサーチは要素を半分に分けるところから始まります。


❷：左端の要素が何番か、と右端の要素が何番かを決めています。配列の一番最初は"0"が当てられるので左端は0,右端は0を含めた要素の数になるので"-1"をしています。(ex:1...15までは10個ありますが、要素は左端は"0"から始まるので右端は"9"になります)


❸：ここでは左からの要素の数と右からの要素の数を比べています。左端の数が右端の数を超えることはないためです。

❹：❹〜❻までバイナリサーチの要の部分です。center_factorで中央の要素を求めました。配列の要素が奇数の場合は自動的に四捨五入をされます。


❺：半分に分け、左右のどちらから検索するのかを決めています。もし中央が探したい番号の場合があるのでreturn で返します。これは❼で出力される形になります。もし中央の要素の中身の数字が、入力した数字ではなかった場合は大小で左端から攻めていくのか右端から攻めていくのかを決めています。入力した値の方が大きければ、左端から検索(この配列は左から右にかけて大きくなっているので）、入力した値の方が小さければ、右端から検索(この配列は右から左にかけて小さくなっているので）しています。そうするとまた❹-❺をwhile文によって繰り返します。


❻：検索した数字が見つからなかった場合を指します。"0"or"1"でoff,onを判定をするのが一般的ですが、吐配列の要素で"0"を使用しているので"-1"でわかりやすく表現しています。


❼：最後に、検索された結果を出力しています。

4.ここから学んだこと（エラーの時に使用） ---------------------------------------- の部分で”.round"をつけなくてもいいのかな？と思って調べてみると自動的に四捨五入されるようです。指定の位で四捨五入する際は".round(2)<小数第2位までを表示するので小数第3位で四捨五入されます>"などでコーディングしてあげると便利に使えます！