Ruby#Index Method VS Binary Search

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.

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!

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

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

Ruby Binary Search Code is Not Returning Expected Results

A prerequisite :

• 4 + 4 / 2 will give us 6. It's the equivalent of 4 + (4 / 2 ).
• (4 + 4) / 2 will give us 4.

The two statements are not equivalent.

On the two middle computation :

middle = first + last / 2

We do not have what we expect.

You are looking to divide first AND last by two.
So you will want to have :

middle = (first + last) / 2

If you replace first + last / 2 by (first + last) / 2, your script will give us :

binary_search(4, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
we're in the else and middle is now 2
we're in the elsif and middle is 3
we've found the target! middle is 3
 => true 

Strange behavior with bsearch_index

You need to write

tmp.bsearch_index{|n| n >= -3}    #=> 0

This uses Array#bsearch_index's find minimum mode, which returns the smallest value in the array that satisfies the expression in the block. For example,

tmp.bsearch { |n| n >= 0 }        #=> 3
tmp.bsearch_index { |n| n >= 0 }  #=> 1

In this mode, to quote the doc for Array#bsearch, "the block must always return true or false, and there must be an index i (0 <= i <= ary.size) so that the block returns false for any element whose index is less than i, and the block returns true for any element whose index is greater than or equal to i. This method returns the i-th element. If i is equal to ary.size, it returns nil."

If the block were { |n| n == -3 } there would be no index i, 0 <= i <= tmp.size #=> 3 that has the property that tmp[j] == -3 is false for all j < i and true for all j >= 1.

If the block calculation were tmp[j] == 5 the requirement would be satisfied (for index 2) so the correct value would be returned. If the block calculation were tmp[j] == 3 the requirement would not be satisfied (tmp[2] == 3 #=> false); the fact that the correct index is returned is only due to the way the method has been implemented. If

tmp = [-3, 3, 5, 6]

then nil is returned for n == 3 as well as for n == -3:

tmp.bsearch_index { |n| n == 3 }  #=> nil

bsearch has a second mode, find any mode. (See the doc for Array#bsearch for details.) In this case we might write one of the following:

tmp.bsearch_index { |n| -3 - n }  #=> 0   
tmp.bsearch_index { |n|  3 - n }  #=> 1
tmp.bsearch_index { |n|  5 - n }  #=> 2
tmp.bsearch_index { |n|  4 - n }  #=> nil

This mode would be useful here if nil were to be returned when no element in the array evaluates to zero in the block. In other contexts it has a multitude of uses.

How to write a binary search method if value might not be in array

Is this homework? If not, then just use Array#bsearch.

If it is homework, then consider what happens when you reach the point that you have no more values to test; your to will be <= your from (that is, the size of your search space is empty - there are no more values left to test). In the case that happens, you should raise an exception or return some value which is interpreted as "value not found".

---

Related Topics