【Ruby】バイナリーサーチを用いた配列内の要素検索

配列内に任意の値が存在するかを確認するプログラムを作成します。
任意の値が配列内に存在しない場合は、「値は配列内に存在しません」と表示し、存在する場合は、配列の何番目にあるかを表示します。

今回のプログラムではバイナリーサーチという、配列を2分割した検索方法を用います。
例えば以下のような配列がある場合、中央値である「3」から左右と比較して検索する手法です。
これにより検索したい値が「1」であった場合、「4,5」は比較を行わないため処理速度の向上につながります。

ruby

array = [1, 2, 3, 4, 5]

回答例

ruby

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          //arrayの「1,3,5,6,9」を対象外とする設定
    else
      right = center - 1         //それ以外の場合、arrayの「9,10,13,20,26,31」を対象外とする設定
    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

解説

まずはメソッド外。

1. 配列「array」の準備
2. 任意の文字「target」の準備
3. 配列の要素数「number_of_elements」の準備
   これら3つの変数を実引数に設定し「binary_serach」メソッドを実行しています。

続いてメソッド内。

1. 配列の先頭及び末尾の配列番号を「left」「right」に代入。
2. while文にて、この「left」「right」の値が逆転するまで繰り返しを行う設定。
3. 以下の記述で中央値の配列番号を取得しています。今回の配列の要素は偶数個であるため、「(0+9) / 2 = 4.5」となります。配列番号4.5は存在しませんが、rubyにおける計算式の小数点は切り捨てられるため、今回の配列における中央値は「array[4] = 9」となります。

ruby

「center = (left + right) / 2」

if文による条件分岐を行い、左右のどちらに値が存在するかを繰り返し判定します。
最終的に配列内に任意の値が存在しなかった場合は「return -1」という返り値を渡してメソッドを終了します。

最後に再びメソッド外。

1. 任意の値が存在しなかった場合は「-1」が戻ってくるので、存在しない旨のメッセージを出力。
2. 任意の値が存在した場合は正しい値が戻ってくるので、存在する箇所を出力。

バイナリーサーチ知らないと思いつかない方法だと思いますので、しっかり覚えておきたいです。
ご意見等ございましたらコメントをいただけますと幸いです。