2分探索（バイナリサーチ）

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

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

Ruby でやりました。
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教科書)

p.32
　

※追記（2018/2/8）
関数型プログラミングっぽく…。ちょっと計算はわかりにくいかも知れませんが、ロジックは明快です。配列 ar の真ん中を取って、それが探す数値なら idx を返し、そうでない場合、ar を分割して左側と右側のゴールのある方を選んで再帰します。i は配列 ar の真ん中のインデックスで、idx は i が最初に与えられた配列のどのインデックスになるか保持しています。なので探索が終われば idx を返せばいいのです。
binary_search1.rb

class Array
  def binary_search(n)
    bs = lambda do |ar, i, idx|
      return nil unless ar[i]
      return idx if ar[i] == n
      if ar[i] > n
        bs.call(ar[0..i - 1], a = (i - 1) / 2, idx - i + a)
      else
        bs.call(ar[i + 1..-1], a = (ar.size - i - 1) / 2, idx + a + 1)
      end
    end
    bs.call(self, 0, 0)
  end
end

配列に含まれない数字を探索すると nil が返ります。