Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Source of article about binary search at Gistflow.com
class Array
def bindex element, lower = 0, upper = length - 1
return if lower > upper
mid = (lower + upper) / 2
element < self[mid] ? upper = mid - 1 : lower = mid + 1
element == self[mid] ? mid : bindex(element, lower, upper)
end
end
class Array
def iterative_bindex element, lower = 0, upper = length - 1
while upper >= lower
mid = (upper + lower) / 2
if self[mid] < element
lower = mid + 1
elsif self[mid] > element
upper = mid - 1
else
return mid
end
end
return nil
end
end
require 'test/unit'
class TestArrayBindex < Test::Unit::TestCase
def self.it name, &block
define_method("test_#{name.gsub(/\W/,'_')}", &block) if block
end
it 'should give same results as Array#index' do
array = (1..100).to_a
1.upto 100 do |i|
assert_same array.bindex(i), array.index(i)
end
end
it 'should return nil for empty array' do
assert_same [].bindex(3), nil
end
it 'should return 0 for array with 1 element' do
assert_same [3].bindex(3), 0
end
it 'should return right index for array with 2 elements' do
array = [1, 2]
assert_same array.bindex(1), 0
assert_same array.bindex(2), 1
end
it 'should return nil if there is no such element in array' do
array = (1..100).to_a
array.delete 75
assert_same array.bindex(0), nil
assert_same array.bindex(101), nil
assert_same array.bindex(75), nil
end
end
require 'benchmark/ips'
Benchmark.ips do |r|
array = (1..100).to_a
r.report 'binary' do
array.bindex 25
array.bindex 75
end
r.report 'rindex' do
array.rindex 25
array.rindex 75
end
r.report 'index' do
array.index 25
array.index 75
end
r.report 'iterative bindex' do
array.iterative_bindex 25
array.iterative_bindex 75
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment