Skip to content

Instantly share code, notes, and snippets.

@kastner
Created April 25, 2010 23:54
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kastner/378840 to your computer and use it in GitHub Desktop.
Save kastner/378840 to your computer and use it in GitHub Desktop.
# user system total real
# real_bsearch best-case 0.370000 0.000000 0.370000 ( 0.367332)
# real_bsearch worst-case 6.590000 0.000000 6.590000 ( 6.602298)
# real_recursive_bsearch best-case 0.200000 0.000000 0.200000 ( 0.195659)
# real_recursive_bsearch worst-case 6.950000 0.010000 6.960000 ( 6.958505)
# bsearch best-case 12.000000 0.180000 12.180000 ( 12.200769)
# bsearch worst-case 12.670000 0.180000 12.850000 ( 12.890500)
# recursive_bsearch best-case 32.840000 0.050000 32.890000 ( 32.988642)
# recursive_bsearch worst-case 35.670000 0.100000 35.770000 ( 37.023431)
require 'benchmark'
n = 5_000_000
ar = (1..n).to_a
Benchmark.bm do |x|
%w[real_bsearch real_recursive_bsearch bsearch recursive_bsearch].each do |meth|
x.report("#{meth} best-case") { 100_000.times do; send(meth, n/2, ar); end }
x.report("#{meth} worst-case") { 100_000.times do; send(meth, -1, ar); end }
end
end
# One possible bug is that each element in haystack doesn't
# respond to the comparison operators.
# That can be fixed by doing
# return nil unless haystack.all? {|e| e.respond_to?("<=>")}
# but that takes a LOG(2)N algo and makes it N * LOG(2)N
# since the requirement is a "sorted array", that implies that each
# element is comparable.
def bsearch(needle, haystack)
return nil unless needle && haystack
return nil unless %w![] empty? each!.all? {|op| haystack.respond_to?(op)}
return nil unless needle.respond_to?("<=>")
return nil if haystack.empty?
valid_range = haystack
loop do
return false if valid_range.empty?
mid = valid_range.size / 2
return needle if valid_range[mid] == needle
r = valid_range[mid] > needle ? 0...mid : mid+1..-1
valid_range = valid_range[r]
end
end
def real_bsearch(needle, haystack)
left, right = [0, haystack.size - 1]
loop do
return false if right < left
mid = (right - left) / 2 + left
return needle if haystack[mid] == needle
(left, right) = haystack[mid] > needle ? [left, mid - 1] : [mid + 1, right]
end
end
def real_recursive_bsearch(needle, haystack, left=0, right=haystack.size-1)
return false if right < left
mid = (right - left) / 2 + left
return needle if haystack[mid] == needle
(left, right) = haystack[mid] > needle ? [left, mid - 1] : [mid + 1, right]
real_recursive_bsearch(needle, haystack, left, right)
end
def recursive_bsearch(needle, haystack)
return nil unless needle && haystack
return nil unless %w![] empty? each!.all? {|op| haystack.respond_to?(op)}
return nil unless needle.respond_to?("<=>")
return false if haystack.empty?
mid = haystack.size / 2
return needle if haystack[mid] == needle
range = haystack[mid] > needle ? 0...mid : mid+1..-1
return recursive_bsearch(needle, haystack[range])
end
require 'test/unit'
class TestIt < Test::Unit::TestCase
def assert_both(n, h, m="")
assert bsearch(n, h) == n, m
assert recursive_bsearch(n, h) == n, m
end
def assert_neither(n, h, m="")
assert !bsearch(n, h), m
assert !recursive_bsearch(n, h), m
end
def test_simple
assert_both 1, [1, 2, 3]
end
def test_empty
assert_neither 1, []
end
def test_three_elements
assert_both 1, [1, 2, 3]
assert_both 2, [1, 2, 3]
assert_both 3, [1, 2, 3]
assert_neither 4, [1, 2, 3]
assert_neither -1, [1, 2, 3]
end
def test_lots
tests = `curl -s http://www.mac-guyver.com/switham/2010/04/Binary_Search/tests.txt.gz | zcat`
tests.scan(/(P.+?)\n(.+?)\nin \[\n([^\]]*)\]\? (yes|no)/m).each do |m|
method = m[-1] == "yes" ? :assert_both : :assert_neither
send method, m[1].to_i, m[2].split("\n").map {|l| l.to_i}, m[0]
end
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment