Is There a Built-In Binary-Search in Ruby

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

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!

Ruby#index Method VS Binary Search

The built-in #index is not a binary search, it's just a simple iterative search. However, it is implemented in C rather than Ruby, so naturally it can be several orders of magnitude faster.

Weird binary search behavior in Ruby

This is what you ask for after I edited my question. Problem with the code was you were splitting into new array so 34 was the only element at that array at the end therefore index was 0.

class Searcher
def binary_search(array, val, low=0, high=(length - 1))
return nil if high < low
mid = (low + high) >> 1
case val <=> array[mid]
when -1
binary_search(array, val, low, mid - 1)
when 1
binary_search(array, val, mid + 1, high)
else mid
end
end
end

arr = [1,3,4,12,16,21,34,45,55,76,99,101]
key = 34
s = Searcher.new
index = s.binary_search(arr, key, 0, arr.length)
puts index

manual binary search wrap up

half was part of the problem. With a length of 2, half would be 0, and you would "split" your array in a full array and an empty array : recursion would never end.

You also need to keep an index, and add half to it when you consider the 2nd Array :

def binary_search(letter, array, i=0)
puts "Been here for #{array} with #{i}"
half = array.length / 2
if letter == array[half]
return i + half
end
if letter > array[half] && letter <= array[-1]
binary_search(letter, array.drop(half), i + half)
elsif letter < array[half] && letter >= array[0]
binary_search(letter, array.take(half), i)
else
nil
end
end

arr = [:A, :B, :C, :D, :E, :F, :G]
p binary_search(:C, arr)
p binary_search(:G, arr)

It outputs

Been here for [:A, :B, :C, :D, :E, :F, :G] with 0
Been here for [:A, :B, :C] with 0
Been here for [:B, :C] with 1
2
Been here for [:A, :B, :C, :D, :E, :F, :G] with 0
Been here for [:D, :E, :F, :G] with 3
Been here for [:F, :G] with 5
6

Using bsearch to find index for inserting new element into sorted array

You can use the Enumerator object returned by each_with_index to return a nested array of [value, index] pairs and then conduct your binary search on that array:

a = [1,2,4,5,6]
new_elm = 3

index = [*a.each_with_index].bsearch{|x, _| x > new_elm}.last
=> 2

a.insert(index, new_elm)

EDIT:

I've run some simple benchmarks in response to your question with an array of length 1e6 - 1:

require 'benchmark'

def binary_insert(a,e)
index = [*a.each_with_index].bsearch{|x, _| x > e}.last
a.insert(index, e)
end

a = *1..1e6
b = a.delete_at(1e5)
=> 100001

Benchmark.measure{binary_insert(a,b)}
=> #<Benchmark::Tms:0x007fd3883133d8 @label="", @real=0.37332, @cstime=0.0, @cutime=0.0, @stime=0.029999999999999805, @utime=0.240000000000002, @total=0.2700000000000018>

With this in mind, you might consider trying using a heap or a trie instead of an array to store your values. Heaps in particular have constant insertion and removal time complexities, making them ideal for large storage applications. Check out this article here: Ruby algorithms: sorting, trie, and heaps

How to find the insertion point in an array using binary search?

This is the code from Java's java.util.Arrays.binarySearch as included in Oracles Java:

    /**
* Searches the specified array of ints for the specified value using the
* binary search algorithm. The array must be sorted (as
* by the {@link #sort(int[])} method) prior to making this call. If it
* is not sorted, the results are undefined. If the array contains
* multiple elements with the specified value, there is no guarantee which
* one will be found.
*
* @param a the array to be searched
* @param key the value to be searched for
* @return index of the search key, if it is contained in the array;
* otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
* <i>insertion point</i> is defined as the point at which the
* key would be inserted into the array: the index of the first
* element greater than the key, or <tt>a.length</tt> if all
* elements in the array are less than the specified key. Note
* that this guarantees that the return value will be >= 0 if
* and only if the key is found.
*/
public static int binarySearch(int[] a, int key) {
return binarySearch0(a, 0, a.length, key);
}

// Like public version, but without range checks.
private static int binarySearch0(int[] a, int fromIndex, int toIndex,
int key) {
int low = fromIndex;
int high = toIndex - 1;

while (low <= high) {
int mid = (low + high) >>> 1;
int midVal = a[mid];

if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}

The algorithm has proven to be appropriate and I like the fact, that you instantly know from the result whether it is an exact match or a hint on the insertion point.

This is how I would translate this into ruby:

# Inserts the specified value into the specified array using the binary
# search algorithm. The array must be sorted prior to making this call.
# If it is not sorted, the results are undefined. If the array contains
# multiple elements with the specified value, there is no guarantee
# which one will be found.
#
# @param [Array] array the ordered array into which value should be inserted
# @param [Object] value the value to insert
# @param [Fixnum|Bignum] from_index ordered sub-array starts at
# @param [Fixnum|Bignum] to_index ordered sub-array ends the field before
# @return [Array] the resulting array
def self.insert(array, value, from_index=0, to_index=array.length)
array.insert insertion_point(array, value, from_index, to_index), value
end

# Searches the specified array for an insertion point ot the specified value
# using the binary search algorithm. The array must be sorted prior to making
# this call. If it is not sorted, the results are undefined. If the array
# contains multiple elements with the specified value, there is no guarantee
# which one will be found.
#
# @param [Array] array the ordered array into which value should be inserted
# @param [Object] value the value to insert
# @param [Fixnum|Bignum] from_index ordered sub-array starts at
# @param [Fixnum|Bignum] to_index ordered sub-array ends the field before
# @return [Fixnum|Bignum] the position where value should be inserted
def self.insertion_point(array, value, from_index=0, to_index=array.length)
raise(ArgumentError, 'Invalid Range') if from_index < 0 || from_index > array.length || from_index > to_index || to_index > array.length
binary_search = _binary_search(array, value, from_index, to_index)
if binary_search < 0
-(binary_search + 1)
else
binary_search
end
end

# Searches the specified array for the specified value using the binary
# search algorithm. The array must be sorted prior to making this call.
# If it is not sorted, the results are undefined. If the array contains
# multiple elements with the specified value, there is no guarantee which
# one will be found.
#
# @param [Array] array the ordered array in which the value should be searched
# @param [Object] value the value to search for
# @param [Fixnum|Bignum] from_index ordered sub-array starts at
# @param [Fixnum|Bignum] to_index ordered sub-array ends the field before
# @return [Fixnum|Bignum] if > 0 position of value, otherwise -(insertion_point + 1)
def self.binary_search(array, value, from_index=0, to_index=array.length)
raise(ArgumentError, 'Invalid Range') if from_index < 0 || from_index > array.length || from_index > to_index || to_index > array.length
_binary_search(array, value, from_index, to_index)
end

private
# Like binary_search, but without range checks.
#
# @param [Array] array the ordered array in which the value should be searched
# @param [Object] value the value to search for
# @param [Fixnum|Bignum] from_index ordered sub-array starts at
# @param [Fixnum|Bignum] to_index ordered sub-array ends the field before
# @return [Fixnum|Bignum] if > 0 position of value, otherwise -(insertion_point + 1)
def self._binary_search(array, value, from_index, to_index)
low = from_index
high = to_index - 1

while low <= high do
mid = (low + high) / 2
mid_val = array[mid]

if mid_val < value
low = mid + 1
elsif mid_val > value
high = mid - 1
else
return mid # value found
end
end
-(low + 1) # value not found.
end

Code returns the same values as OP provided for his test data.

Ruby Array #bsearch syntax error from Programming Ruby?

Having tested your code myself, there is nothing wrong with what you have written. In all likelihood you (or in this case, codecademy) are using an older version of Ruby. The bsearch method was defined on Array and Range in Ruby 2.0. Prior to Ruby 2.0, there were several gems that could be used to perform a binary search on an array.

To test which version of Ruby you are using, type the following into irb or your codecademy console:

> RUBY_VERSION
=> "2.1.1"

If the number returned is less than "2.0", bsearch will not be natively defined for either Array or Range

Is there a Ruby built-in class or module (other than String) that has method #to_str?

The easiest way is to ask Ruby herself:

ObjectSpace.
each_object(Module).
select {|mod| mod.instance_methods(false).include?(:to_str) } -
[String]
#=> [NameError::message]

So, it turns out the only other class that defines to_str is an internal implementation class inside NameError. Which makes sense, really, there are not that many objects in Ruby that are strings but are not instances of String.

I would expect a Ropes library (if such a thing exists) to implement to_str, for example.

anything faster than .include?

I agree with @mu, however if you really want to use an array, and are using Ruby 2.0.0, you might want to check out the bsearch method.

arr = [1,2,3,5,6]
arr.bsearch { |x| 3 == x } # => 3
arr.bsearch { |x| 7 == x } # => nil

arr1 = ['1','2','3','4','5','6']
arr1.bsearch { |x| '2' == x } # => "2"
arr1.bsearch { |x| '7' == x } # => nil

http://www.ruby-doc.org/core-2.0/Array.html#method-i-bsearch



Related Topics



Leave a reply



Submit