Skip to content

Instantly share code, notes, and snippets.

@stangel
Created November 29, 2017 22:54
Show Gist options
  • Save stangel/003cd8b663b88476b5a06cba254a2bcf to your computer and use it in GitHub Desktop.
Save stangel/003cd8b663b88476b5a06cba254a2bcf to your computer and use it in GitHub Desktop.
Bisect a proc that takes two numeric arguments and raises an exception when the error condition is between them
def bisect(start_num, end_num, test_proc)
# calling test_proc(start_num, end_num) should raise an exception on failure
legit_exceptions = [SystemExit, NoMethodError]
initial_fail = nil
begin
test_proc.call(start_num, end_num)
rescue Exception => e
e.reraise if legit_exceptions.include?(e.class)
initial_fail = true
end
raise("test_proc should raise an exception when called with #{start_num} and #{end_num}!") unless initial_fail
n1 = start_num
n2 = end_num
while true
return start_num if start_num == end_num
break if n2 == n1 + 1
mid = (n1 + n2) / 2
begin
test_proc.call(mid, n2)
# if we get here, the test passed
n2 = mid
rescue Exception => e
e.reraise if legit_exceptions.include?(e.class)
# if we get here, the test failed
n1 = mid
end
end
# if we get here, n2 = n1 + 1 (imperfect bisection) -- test each individually
begin
test_proc.call(n1, n1)
rescue Exception => e
e.reraise if legit_exceptions.include?(e.class)
return n1
end
begin
test_proc.call(n2, n2)
rescue Exception => e
e.reraise if legit_exceptions.include?(e.class)
return n2
end
return "Inconclusive -- got to #{n1}, #{n2}"
end
# test it -- should return 63
bisect(0, 100, lambda {|a,b| puts "#{a}, #{b}" ; raise('fail') if a <=63 and b >= 63})
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment