一致したメンバーが複数あるとき、そのうちの最初のメンバーを返すバイナリサーチ
横着プログラミング 第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