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

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

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

binary_search.rb(2017/6/30 修正)

class Array
  def binary_search(n)
    ar = dup
    i = ar.size / 2
    return nil if n < ar[0] or n > ar[-1]
    return i if ar[i] == n
    if ar[i] < n
      i + 1 + ar.select{|x| x > ar[i]}.binary_search(n) rescue nil
    else
      ar.select {|x| x < ar[i]}.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教科書)

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

p.32