バイナリーサーチを使って配列の中の値を検索するコード

今日も学んだことを忘れない為にメモします。

バイナリーサーチとは

ソート（データを順に並べ替える）済みのリストや配列に入ったデータ（同一の値はないものとする）に対する検索を行うときに用いられる手法。まず、中央の値を確認し、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断する。
それを繰り返し、片側には存在しないことを確かめながら検索していく方法。

二分探索、二分割検索とも呼び、1回の処理で選択肢が半分になるので、処理速度の向上が期待できる。

プログラム内容

配列 array=[1, 3, 5, 6, 9, 10, 13, 20, 26, 34]があり、任意の値が存在するかどうか、そして何番目に存在するのか、検索する。
任意の値が配列内に存在しない場合は、「値は配列内に存在しません」と表示し、
存在する場合は、配列の何番目にあるかを表示する。
配列における「1」は「配列の0番目に存在する」と表現と表現する。

"" 記述内容

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

検索したい値はtarget
一番左側の添え字はleft（left = 0）
一番右側の添え字はright（lengthメソッドを使用して配列の要素数を取得して一番右側の添え字とする）
真ん中の添え字はcenter（center = (left + right) / 2で真ん中の添え字を求める）（Rubyでは小数点以下は切り捨てになる）
に代入する。

以下がバイナリーサーチを使った処理の部分

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

while文を使用して、当てはまるまで計算を繰り返していく。
※return -1は何も当てはまるときがないときに、最終的な返り値になる。
targetとして31を入力した場合、

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

1回目の検索では、
left = 0
right = 10
となり、中央の値がある添え字はcenter = (left + right) / 2で
center=5
となり中央の値がある添え字が分かったので検索したい値と比較する。

array[center] =10
target　= 31
となるので
array[center] < target となる
これで次に検索すべき範囲は以下になる

[13,20,26,31]

centerの一つ右側へ変更になるので、left = center ＋ 1となる
（真ん中の添え字が一番左側の添え字になる場合はleft = center ＋ 1
真ん中の添え字が一番右側の添え字になる場合はright = center - 1
となる）

2回目の検索では
left= 6
right=　10
となり、中央の値がある添え字はcenter = (left + right) / 2で
center=8
となり中央の値がある添え字が分かったので検索したい値と比較する。

array[center]=26
target　= 31
となるので
array[center] < target となる
これで次に検索すべき範囲は以下になる

[26,31]

centerの一つ右側へ変更になるので、left = center ＋ 1となり、結果array[center]=３１となる。
target　= 31なので array[center] == targetとなりreturn centerによってメソッド内の処理から抜け出し返り値が9となる。

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

の処理で"31は配列の9番目に存在します"と出力される。

以上になります。