一致したメンバーが複数あるとき、そのうちの最初のメンバーを返すバイナリサーチ

横着プログラミング 第9回: sary: Suffix Array のライブラリとツールを読んでSuffixArrayの場合のバイナリサーチは、「一致したメンバーが複数あるとき、そのうちの最初のメンバーを返す」方が都合がいいなと思いました。で、高林さんのページのプログラムをRubyに移植してみました。

#!/usr/bin/env ruby

class Array
  def bsearch_index_first(key, low = -1, high = self.size, &comp)
    comp ||= proc {|key, elem| key <=> elem }
    if low + 1 == high
      return -1 if high >= self.size or comp.call(key, self[high]) != 0
      return high
    end
    mid = (low + high) / 2
    if comp.call(key, self[mid]) > 0
      bsearch_index_first(key, mid, high, &comp)
    else
      bsearch_index_first(key, low, mid, &comp)
    end
  end
end

ary = [10, 11, 12, 12, 14, 15, 16]
p ary.bsearch_index_first(10) # => 0
p ary.bsearch_index_first(11) # => 1
p ary.bsearch_index_first(12) # => 2
p ary.bsearch_index_first(13) # => -1
p ary.bsearch_index_first(14) # => 4
p ary.bsearch_index_first(15) # => 5
p ary.bsearch_index_first(16) # => 6