Source of article about binary search at Gistflow.com

bindex.rb

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