Skip to content

Instantly share code, notes, and snippets.

@betacar
Created February 11, 2017 20:29
Show Gist options
  • Save betacar/45daf64ae4cba31d6c61cc747a461f25 to your computer and use it in GitHub Desktop.
Save betacar/45daf64ae4cba31d6c61cc747a461f25 to your computer and use it in GitHub Desktop.
Algorithms
require 'benchmark'
Benchmark.bm do |bm|
def binary_search arr, target
med = (arr.length / 2).to_i
return false if med == 1
val = arr[med]
return true if val == target
if val < target
return binary_search arr[med..(arr.size - 1)], target
end
if val > target
return binary_search arr[0..med], target
end
false
end
def search arr, target
for val in arr
return true if val == target
end
false
end
range = (0..1_000_000).to_a
num = range.to_a.sample
bm.report {
binary_search range, num
}
bm.report {
search range, num
}
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment