Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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?

like image 238
Jonah Avatar asked Dec 29 '11 19:12

Jonah


People also ask

How to do binary search in Ruby?

You can make a ruby file such as binary_search. rb in your code editor of choice and run the algorithm by running in your terminal the command "ruby binary_search. rb".

What does .first mean in Ruby?

The first() is an inbuilt method in Ruby returns an array of first X elements. If X is not mentioned, it returns the first element only. Syntax: range1.first(X) Parameters: The function accepts X which is the number of elements from the beginning. Return Value: It returns an array of first X elements.

How does the binary search algorithm work?

Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you've narrowed down the possible locations to just one.

How does Ruby find work?

The find method locates and returns the first element in the array that matches a condition you specify. find executes the block you provide for each element in the array. If the last expression in the block evaluates to true , the find method returns the value and stops iterating.


2 Answers

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!

like image 67
Marc-André Lafortune Avatar answered Sep 28 '22 06:09

Marc-André Lafortune


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 }

like image 35
Yoav Epstein Avatar answered Sep 28 '22 05:09

Yoav Epstein