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
Rails 3.1 Pipeline - Exclude JavaScript File
How to Prevent Nokogiri from Adding <Doctype> Tags
Why Many People Use "-%>" Instead of "%>" in Rails
Double-Splat Operator Destructively Modifies Hash - Is This a Ruby Bug
How to Reverse a 'Rails Generate'
How to Check for File Existence
In Rails, Display Time Between Two Dates in English
Can Rails Migrations Be Used to Convert Data
Rails Forms for Has_Many Through Association with Additional Attributes
What Does 'Def Self.Function' Name Mean
How to Reference a Function in Ruby
Ruby: Dynamically Generate Attribute_Accessor
Uninstall Old Versions of Ruby Gems
How to Sort an Array of Hashes by a Value in the Hash
Running Pod Setup Gives Me "Bad Interpreter: No Such File or Directory" Error