binsearch.rb

#!/usr/bin/env ruby
#
# Are you one of the 10% of programmers who can write a binary search?
# http://reprog.wordpress.com/2010/04/19/are-you-one-of-the-10-percent/

def bin_search(search, subject)

  discarded_left = 0

  while subject.any?

    mid = subject.length / 2
    comparison = search <=> subject[mid]

    return comparison.zero? ? discarded_left : nil if subject.one?

    case comparison
      when -1
        subject = subject[0...mid]
      when 1
        subject = subject[mid...subject.length]
        discarded_left += mid
      else
        return discarded_left + mid
    end

  end

end


###
# Tests

$passes = 0
$fails = 0

def assert_bin_search(expect, search, subject)
  found = bin_search(search, subject);
  pass = found === expect
  puts "FAIL: search:%d expect:%s got:%s in [%s]" %
    [search, expect.inspect, found.inspect, subject.join(',')] unless pass
  pass ? $passes += 1 : $fails += 1
end

subject = [4, 5, 7, 11, 19, 29, 42, 69, 129, 182, 189, 190, 250]

# test each value
subject.each_with_index do |value, index|
  assert_bin_search(index, value, subject)
end

# test out-of-bounds and gaps
((0..500).to_a - subject).each do |value|
  assert_bin_search(nil, value, subject)
end

# test empty subject
assert_bin_search(nil, 1, [])

puts "Passes: #{$passes}  Fails: #{$fails}"

output.txt

paulbookpro:binsearch paul$ ./binsearch.rb 
Passes: 502  Fails: 0