Ruby1.9以前でバイナリサーチ

Ruby2.0以降はArray#bsearchが、2.3以降はArray#bsearch_indexが標準でありますが、どうしても1.9を使わなければいけないことがあったので、自前で実装しました。
仕様としてはRuby2.0のArray#bsearchのfind-minimumモードと同じにしてあります。

bsearch.rb

class Array
  def bsearch(&block)
    index = bsearch_index(&block)
    index.nil? ? nil : self[index]
  end

  def bsearch_index(&block)
    return nil if length == 0
    bsearch_impl(self, &block)
  end

  def bsearch_impl(ary, &block)
    if ary.length == 1
      return block.call(ary[0]) ? 0 : nil
    end

    index = ary.length / 2

    if block.call(ary[index])
      recursion = bsearch_impl(ary.slice(0..(index - 1)), &block)
      recursion || index
    else
      recursion = bsearch_impl(ary.slice(index..-1), &block)
      recursion ? recursion + index : nil
    end
  end

  private :bsearch_impl
end

真ん中の要素でブロックを実行して、trueが返ればそれ以前の部分配列に、falseなら後ろの部分配列に対して再帰的にbsearch_implを適用しています。
再帰を使ってはいますがバイナリサーチなので、スタックが溢れるほど再帰が深くなることはない、はず……

ろくにテストもしてないので、バグがあったらツッコんでやってくださいｗ