Rubyでlower_bound

C++のSTLにある、その値以上の要素のインデックスを見つける関数

lower_bound.rb

def lower_bound(array, value)
  left = -1;
  right = array.length;
  while left + 1 < right
    mid = left + (right - left) / 2;
    if array[mid] >= value
      right = mid
    else
      left = mid
    end
  end
  right
end

参考

• Rubyで2分探索 http://qiita.com/saytx@github/items/74eb27bb98641ba05b2f
• 二分探索 http://topcoder.g.hatena.ne.jp/cafelier/20120703/1341324546