バイナリーサーチを利用して要素を検索する

調べたことを整理して落とし込めるためにまとめます。
Rubyを使用しています。

バイナリーサーチとは

データの検索をする際に用いられる手法のことを言います。

• ソート済みのデータ
• 同一の値が存在しない配列に入ったデータ

などが対象です。

検索したい値 = A
リストの中央に位置する値 = B　
を用意し、AがBより大きければリストの左側にある値を検索対象から除外します。
これを繰り返すことで検索にかかるコストを減らすことができます。

実際に書いたコード

def binary_search(array, num)
  first = 0
  last = array.length - 1

  while first <= last
    center = (first + last) / 2

    if num == array[center]
      return puts "#{num}は配列の#{center}番目に存在します"
    elsif num > array[center]
      first = center + 1
    else
      last = center - 1
    end
  end

  puts "#{num}は配列内に存在しません"
end


array=[1,3,5,6,9,10,13,20,26,31]
puts "検索したい数字を入力してください"
num = gets.to_i
binary_search(array, num)

検索したい値を入力すると、
「○は配列の△番目に存在します」
存在しない値なら
「○は配列内に存在しません」
という結果が返ってきます。

array=[1,3,5,6,9,10,13,20,26,31]
puts "検索したい数字を入力してください"
num = gets.to_i
binary_search(array, num)

この部分で検索したい数字を入力して変数numに代入したのち、変数numと配列arrayをbinary_searchへと渡しています。

def binary_search(array, num)
  first = 0
  last = array.length - 1
  ~省略
end

firstに0を、lastに配列arrayの最後に位置する値の添字を代入しています。
このfirstとlastが検索対象になります。

  while first <= last
    center = (first + last) / 2

while文を使用し、firstはlastよりも小さいという条件式がfalseとなるまで処理を繰り返します。
firstとlastを足して2で割った数を変数centerに代入しています。
これは、配列arrayの中央に位置する値の添字となります。

if num == array[center]
  return puts "#{num}は配列の#{center}番目に存在します"
elsif num > array[center]
  first = center + 1
else
  last = center - 1
end

if文を使用し、検索対象が配列の中央に位置する値を同じであるか、そうでないか、
また、それよりも大きい値であるかを比較しています。
同じ値であったなら配列の何番目に存在するかを表示します。
違う値であったなら、検索対象を限定して再度検索をかけるように処理を記述します。

検索対象が配列の中央に位置する値より大きい値であったなら、firstにcenterに1足した数字を
小さい値であったなら、lastにcenterから1引いた数字を再代入しています。

def binary_search(array, num)
  while first <= last
  ~省略
  end
  puts "#{num}は配列内に存在しません"
end

そうして値が見つかることなくfirstとlastの値が同じになる（配列arrayの最後の値まで検証し終わる）と、while文に指定した条件式の結果がfalseとなり処理が終了します。
そして、○は配列内に存在しませんと表示されます。

コードを書いていて感じたこと

バイナリーサーチを使用して検索をするだけなら、配列arrayの値を再代入しながら限定していくこともできます。
最初はこの方法でコードを書いていました。
ただ、結果として配列の何番目に存在するのかを表示する必要があるため、この方法ではダメだとわかりコードを書き直しました。
色々試行錯誤しましたがなかなか思いつかず、検索をすることにして見つけたのがこの方法です。
コードを読んで理解したことを思い出しながら書きました。
決して丸々コピーなんてしてません。

まとめている中で検索をする処理と、結果を表示する処理は分けたほうが良かったのかな？とも思いました。

コードに関して指摘していただけると勉強の励みになります。