|
#!/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}" |
