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

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?

Jonah

Posted 2011-12-29T19:28:47.087

Reputation: 7 905

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.377

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. – Jonah – 2011-12-29T19:53:44.697

2

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.

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

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

Answers

46

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!

Marc-André Lafortune

Posted 2011-12-29T19:28:47.087

Reputation: 62 249

Hey Marc, Thanks for the answer. Are there any 3rd party libraries (written in C) that I could use? – Jonah – 2011-12-29T19:33:56.290

Looks like there is one. Answer updated. – Marc-André Lafortune – 2011-12-29T19:51:29.760

And @sczizzo linked to another gem too. – Marc-André Lafortune – 2011-12-29T19:52:43.730

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

– ndbroadbent – 2012-11-15T09:44:12.783

2@nathan.f77: Answer edited. backports now include it. – Marc-André Lafortune – 2013-02-23T00:29:42.920

Will this be faster than "include?" which seems to be a linear search? – Rahul – 2013-09-02T09:32:45.343

1@Rahul: Yes, Array#include? is linear so will be slower. – Marc-André Lafortune – 2013-09-02T15:32:24.317

1Is there a way to return the index instead of the value? – Doctor Mohawk – 2015-08-10T20:30:36.940

That's a different question... Post separately and comment back here? – Marc-André Lafortune – 2015-08-10T23:24:44.843

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" – frankpinto – 2016-12-14T20:01:52.010

4

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 }

Yoav Epstein

Posted 2011-12-29T19:28:47.087

Reputation: 316

0

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.

Ruto Collins

Posted 2011-12-29T19:28:47.087

Reputation: 923