Skip to content

Instantly share code, notes, and snippets.

@pda

pda/binsearch.rb

Created Apr 21, 2010
Embed
What would you like to do?
#!/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}"
paulbookpro:binsearch paul$ ./binsearch.rb
Passes: 502 Fails: 0
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment