バイナリーサーチを使って配列の中に任意の値があるか確認する

既にいろんな方が書いている話ではありますが、
書くことによって自分の中で理解を深められたら、と思ったので書きます。

問題

下記の問題をバイナリーサーチを使って解いてみます。

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

# 出力例1
検索したい数字を入力してください
5
5は配列の2番目に存在します

# 出力例2
検索したい数字を入力してください
8
8は配列内に存在しません

そもそもバイナリーサーチとは何か

ソート済みのリストや、配列に入ったデータ（同一の値はないものとする）に対する検索を行うとき、
中央の値を見て、検索したい値との大小関係を用いて、
検索したい値が中央の値の右にあるか、左にあるかを判断して、
片側には存在しないことを確かめながら検索していく方法のこと。
1回の処理で選択肢が半分になるので、処理速度の向上が期待できる。
二分探索、二分割検索ともいう。

どんな感じなのかざっくり書いてみる

検索したい値はtarget、
一番左側の添え字はleft、
一番右側の添え字はright、
真ん中の添え字はcenterに代入することとします。

ちなみに今回はtarget = 5として検索します。

配列を図にすると下記のようになります。

それでは実際にやってみます。

1回目の検索では、
left = 0
right = 9
となり、中央の値がある添え字は
center = (left + right) / 2、つまりcenter = 4となる。
(本当は9を2で割ると4.5だが、Rubyの場合、整数 / 整数 = 整数(小数点以下切り捨て)になるのでこれで大丈夫)
中央の値がある添え字が分かったので検索したい値と比較する。
array[center] = 9
target = 5
なので、array[center] > targetとなる。
これで次に検索すべき範囲がわかる。下の図のようになる。グレーが検索対象外。

図を見て分かる通りrightが変更になる。
centerの一つ左側へ変更になるので、
right = center - 1

もちろんcenterも変わる。求め方は1回目と同じ。
center = (left + right) / 2
ちなみに2回目は計算するとcenter = 1になる。

そして1回目と同じように中央の値と検索したい値を比較。
array[center] = 3
target = 5
なので、array[center] < targetとなる。

そして次の検索範囲が分かる。

今度はleftが変わる。centerの1つ右になるので
left = center + 1
centerも変わる。求め方はこれまでと同じ。
center = (left + right) / 2
ちなみに3回目は計算するとcenter = 2になる。

そしてこれまでと同じように中央の値と検索したい値を比較。
array[center] = 5
target = 5
array[center] == target となり検索終了。

回答例

上記のざっくり書いたものを整理しながら書き直してみます。

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
      right = center - 1
    else
      left = center + 1
    end
  end
  return -1 
end

array = [1, 3, 5, 6, 9, 10, 13, 20, 26, 34]  # 16行目

puts "検索したい数字を入力してください"  # 18行目
target = gets.to_i
elements_num = array.count - 1

result = binary_search(array, elements_num, target)  # 22行目

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

補足

binary_searchメソッドの中にバイナリーサーチに関する記述をしています。

whileで繰り返し処理するように設定しておきます。
繰り返しが有効になる条件は、配列の一番左側の添え字(left)が配列の一番右側の添え字(right)と同じになるまでとしたい(超えたらwhile内の処理はしない)ので、left <= rightとします。

array[center] == targetとなった場合は、
centerの値を返すことと、returnでメソッド内の処理から抜け出すようにしています。

20行目のelements_num = array.count - 1で、配列の一番右側の添え字を取得しています。
countじゃなくてlengthでも良いのかも。

もしソートされてない配列だったら

配列名.sortで並び替えができます。

おわり

eachメソッド使って比べていく方法もありますが、配列の中身が多いほどバイナリーサーチの方が便利ですね。
そういえば昔に友達との間で流行った某アプリってこの仕組みを使用してたのかな。

なんだか長くなってしまいました。最後までお付き合いありがとうございました。