【アルゴリズムの勉強】Rubyで二分探索（バイナリサーチ）を書いてみる

Ruby アルゴリズム

アルゴリズムの勉強としてRubyで二分探索（バイナリサーチ）を実装する。

二分探索とは

ソート済みのリストや配列に入ったデータ（同一の値はないものとする）に対する検索を行うにあたって、 中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく。
大小関係を用いるため、未ソートのリストや大小関係の定義されない要素を含むリストには二分探索を用いることはできない。
n個のデータがある場合、時間計算量はOlog2nである（O記法）。
n個のデータの中央の値を見ることで、1回の操作でn/2個程度（奇数の場合は(n-1)/2個、偶数の場合はn/2個または(n/2)-1個）の要素を無視することができる。

二分探索 - Wikipedia

Rubyで実装

arr = [2, 4, 6, 9, 10, 12, 15, 20, 25, 60]
number_of_elements = arr.count

def binary_search(arr, number_of_elements, target)
  left = 0
  right = number_of_elements - 1

  while left <= right
    center = (left + right) / 2
    if arr[center] == target
      return center
    elsif arr[center] < target
      left = center + 1
    else
      right = center - 1
    end
  end

  return -1
end

target = 20
result = binary_search(arr, number_of_elements, target)
if result == -1
  puts "値が#{target}の要素は配列内に存在しません"
else
  puts "要素の値が#{target}のインデックス => #{result}"
end

参考文献、参考リンク