29

4

I am looking for a built-in Ruby method that has the same functionality as `index`

but uses a binary search algorithm, and thus requires a pre-sorted array.

I know I could write my own implementation, but according to "Ruby#index Method VS Binary Search", the built-in simple iterative search used by index is faster than a pure-Ruby version of binary search, since the built-in method is written in C.

Does Ruby provide any built-in methods that do binary search?

No need to write your own: tyler/binary_search. The author has also taken the time to run some benchmarks.

– sczizzo – 2011-12-29T19:33:51.377Hi sczizzo, I am new to ruby so this is a pretty newb question, but how do I add this functionality to my ruby installation? Is it just a matter of running the rakefile? Thanks. – Jonah – 2011-12-29T19:53:44.697

2

Might be easier to use the

– sczizzo – 2011-12-29T20:15:35.943`bsearch`

gem, as Marc-André suggested. Then it's pretty much as simple as`gem install bsearch`

on the command line, and`require 'bsearch'`

in your Ruby. You might want to look at the documentation for usage.4It should be noted that even if it is written in ruby any implementation of a binary search will eventually outperform any implementation of linear search, no matter how optimized, for large enough arrays. – sepp2k – 2011-12-29T20:31:55.127