[解決済み] Rubyにバイナリ検索は組み込まれていますか？

質問

と同じ機能を持つRubyの組み込みメソッドを探しています。 index が、バイナリ検索アルゴリズムを使用するため、事前にソートされた配列が必要です。

自分で実装を書けるのは分かっているのですが、" によると。 Ruby#indexメソッドVSバイナリサーチ 組み込みのメソッドはCで書かれているため、indexで使用される組み込みの単純な繰り返し検索は、純粋なRubyバージョンのバイナリ検索より高速です。

Rubyにはバイナリサーチを行う組み込みメソッドはありますか？

どのように解決するのですか？

Ruby 2.0導入 Array#bsearch と Range#bsearch .

Ruby 1.9 の場合は bsearch と binary_search の宝石を使用することができます。 他の可能性としては、配列とは異なるコレクションを使用することです。 を使って rbtree

bsearch は私の backports ジェム しかし、これは純粋なRuby版なので、かなり遅いです。純粋なRubyのバイナリ検索は、以下のような線形組み込み検索よりも依然として高速であることに注意してください。 index または include? 十分に大きな配列や範囲（あるいは高価な比較）の場合、同じ程度の複雑さではないので O(log n) 対 O(n) .

今日から遊ぶには require 'backports/2.0.0/array/bsearch' または require 'backports/2.0.0/range/bsearch' .

がんばってください