そろそろ Array#bsearch を組み込んで欲しい

ソート済み配列に対して二分探索する事は結構多いはず。例えば、単純に要素を探したいとき、配列を作るときに挿入ソートで常にソートされた状態に保ちたいとき、など。現状、高林さんの Ruby/Bsearch を使う必要がある。Array に二分探索を入れたがる人はかなり多いはずで、その証拠にこれまで何度も入れろという要望が ruby-dev と ruby-talk で上がっている。最近 (といっても2004年) では、Ruby/Bsearch が 1.9 に標準添付される可能性があったけど、例のごとくメソッド名が嫌われて話自体が消えて行った。また、[ruby-dev:38545] では遠藤さんが Array にソート済みフラグを導入して、ソート済みの場合に内部で二分探索に切り替えて最適化する提案をしているが、色々と問題があって bsearch を導入するより難しそうな印象。

標準添付されるものとしては、Ruby/Bsearch で良いとおもうんだけど、メソッド名がダメだということなので僕なりに考えてみた。追加されるメソッドは次の2つ。

  • Array#bsearch(range=0..n) {|x| ... } #=> A range of indicies
  • Array#bsearch_boundary(range=0..n) {|x| ... } # => A range between upper and lower bounds

前者は、探索条件を満たす最初の添字と最後の添字の Range を返す。
後者は、上限と下限の Range を返す。この Range には upper_boundary と lower_boundary の2メソッドを追加したい。