Ruby binary search of sorted array implemented using deferred detection of equality will return the smallest index found for a matching key attached some tests...

gistfile1.rb

#!/usr/bin/env ruby

require "test/unit"

def binary_search(array, key)
  #binary search of sorted array implemented using deferred detection of equality
  #returns the smallest index found for a matching key
  array = array.sort
  min = 0
  max = array.count - 1
    
  while min < max
    mid = (min + max) / 2
    if (array[mid] < key)
      min = mid + 1
    else
      max = mid
    end      
  end
  #when min == max, if the array contains the key it should be found at the min index
  if max == min and array[min] == key
    puts "found #{key} at index #{min}"
    return {:key => key, :index => min,}
  else
    puts "#{key} not found"
    return {:key => key, :index => nil,}
  end
end


class TestBinarySearch < Test::Unit::TestCase
  
  def setup
    @sorted = [0,1, 2, 3, 3, 4, 5, 6, 6, 8]
    @unsorted = [2,4,7,10,5,3,5,8,11]
    @empty = []
    @two_same= [1,1]
    @two_unsorted=[2,1]
    @two_sorted=[1,2]
  end
 
  def test_sorted
    assert_equal({:key => 0, :index => 0}, binary_search(@sorted, 0))
    assert_equal({:key => 6, :index => 7}, binary_search(@sorted, 6))
    assert_equal({:key => 7, :index => nil}, binary_search(@sorted, 7)) 
  end
  
  def test_unsorted
    assert_equal({:key => 4, :index => 2}, binary_search(@unsorted, 4))
    assert_equal({:key => 5, :index => 3}, binary_search(@unsorted, 5))
    assert_equal({:key => 15, :index => nil}, binary_search(@unsorted, 15))
  end
  
  def test_empty
    assert_equal({:key => 0, :index => nil}, binary_search(@empty, 0))
  end
  
  def test_same
    assert_equal({:key => 1, :index => 0}, binary_search(@two_same, 1))
    assert_equal({:key => 2, :index => nil}, binary_search(@two_same, 2))
  end
  
  def test_two_unsorted
    assert_equal({:key => 2, :index => 1}, binary_search(@two_unsorted, 2))
    assert_equal({:key => 3, :index => nil}, binary_search(@two_unsorted, 3))
  end

  def test_two_sorted
    assert_equal({:key => 2, :index => 1}, binary_search(@two_sorted, 2))
    assert_equal({:key => 3, :index => nil}, binary_search(@two_sorted, 3))
  end
end