Is there a built-in binary-search In Ruby?

Question

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?

Reactor

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

Hi 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. – Reactor

Might be easier to use the 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. – Derk

It 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. – Dieter

Answer 1

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!

Illiberal

Hey Marc, Thanks for the answer. Are there any 3rd party libraries (written in C) that I could use? – Reactor

And @Derk linked to another gem too. – Woodsia

Note that Array#bsearch has now been merged into Ruby: bugs.ruby-lang.org/issues/4766#change-32923 – Rentsch

Will this be faster than "include?" which seems to be a linear search? – Laughter

@Rahul: Yes, Array#include? is linear so will be slower. – Woodsia

Is there a way to return the index instead of the value? – Ply

That's a different question... Post separately and comment back here? – Woodsia

I just tried this on Ruby 2.2.2 and would like to note it doesn't work with ranges of characters. Ex. ('a'..'z').bsearch {|letter| letter == 'b'} fails w/ "TypeError: can't do binary search for String" – Shopworn

@Shopworn You actually can, but you need to convert that range to an array first, and use >= rather than ==. This works: ('a'..'z').to_a.bsearch { |letter| letter >= 'b' } – Foundry

Answer 2

A lot has changed since 2011, in Ruby 2.3, you can use bsearch_index

https://ruby-doc.org/core-2.3.0/Array.html#method-i-bsearch_index

array.bsearch_index { |val| query <=> val }

Resurgent

What's wrong with this? arr = ['a', 'b', 'c', 'd','e'] arr.sort.bsearch { |x| 'a' == x } – Cestus

@AHK try arr.sort.bsearch{ |x| 'a' <=> x } – Lisk

Answer 3

I use bsearch. This is how it works:

array = ['one', 'two', 'three', 'four', 'five']

search = array.sort.bsearch { |value| 'four' <=> value }

Note: binary search needs a sorted array; this adds a li'l overhead but it's fine, compared to the speed of the search.

search will return the value four of the array, else nil if it doesn't find the value.

Rivero