バイナリサーチ - 単なる日記＠はてな

RubyでSuffixArray - 趣味的にっきにおいて「今回は自分でバイナリサーチのアルゴリズムを実装しています。Ruby標準では提供されていないのかな。」と書かれているのを見てbsearchという単語を思い出した。おそらくWe retire raa.ruby-lang.orgのこと。Ruby/Bsearch: a binary search library for Rubyのページ末尾あたりの記述*1にもあるように、一度Rubyへの標準添付が検討されてCVS リポジトリにあるroughモジュールにインポートはされたが、Ruby 1.8.4現在標準添付はされていない。
roughは、既存のライブラリのをRubyへの標準添付を検討する為に用意されたCVS リポジトリのモジュール*2で、実際このディレクトリにあるライブラリの大半がRuby 1.8以降では標準添付されている。Ruby/Bsearchは[ruby-dev:14465] Ruby/Bsearchにおいて標準添付が提案されて、後にroughモジュールにインポートされた。[ruby-dev:23408] Ruby/Bsearchにおいて再度添付を求められて、まつもとさんもメソッド名の検討を条件にしてRuby 1.9への添付を認めたが、そこで話は止まっているようだ。
まとめると、現在Rubyでバイナリサーチを行うには、自分で実装するか、既存のライブラリを利用することになる。RAAにはWe retire raa.ruby-lang.orgのほか、MoonWolfさんによる拡張ライブラリ(We retire raa.ruby-lang.org)が登録されており、アルゴリズム for Rubyには実装のソースコードが公開されている。RubyでSuffixArray - 趣味的にっきの実装(Array#bsearch)もシンプルなので使いやすいと思う。

*1:CVS リポジトリへのリンクが古いURLを指している。現在はsvn.ruby-lang.orgにある

*2:……のはず。それが明言されている記述はどこだっけ。