読者です 読者をやめる 読者になる 読者になる

2分探索(バイナリサーチ)

Ruby アルゴリズム

練習問題 2.3-5
数字の入った配列の中から、引数に一致する要素のインデックスを返します。そのような要素がなければ nil を返します。配列はソートされている必要があります。

マージソートのように、配列を再帰的に半分づつにしていって探します。最悪実行時間は Θ(lg n) です。

binary_search.rb

class Array
  def binary_search(n)
    a = self
    return nil if a[0] > n or a[-1] < n
    i = a.size / 2
    return i if a[i] == n
    if a[i] < n
      i + 1 + a[(i + 1)..-1].binary_search(n) rescue nil
    else
      a[0..(i - 1)].binary_search(n)
    end
  end
end

p [1, 3, 4, 9, 10, 15].binary_search(4)    #=>2

組み込みメソッドなら

p [1, 3, 4, 9, 10, 15].index(4)    #=>2

でお仕舞。


アルゴリズムイントロダクション 第3版 第1巻: 基礎・ソート・データ構造・数学 (世界標準MIT教科書)』p.32