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?
Ruby 2.0 introduced Array#bsearch
and Range#bsearch
.
For Ruby 1.9, you should look into the bsearch
and binary_search
gems.
Other possibility is to use a different collection than an array, like using rbtree
bsearch
is in my backports
gem, but this is a pure Ruby version, so quite a bit slower. Note that a pure Ruby binary search will still be faster than a linear builtin search like index
or include?
for big enough arrays/ranges (or expensive comparisons), since it's not the same order of complexity O(log n)
vs O(n)
.
To play with it today, you can require 'backports/2.0.0/array/bsearch'
or require 'backports/2.0.0/range/bsearch'
.
Good luck!