Ruby linear search and binary search performance testing
Searching for 648248 in sorted array | |
user system total real | |
linear 34.070000 0.040000 34.110000 ( 34.127835) | |
native binary 0.000000 0.000000 0.000000 ( 0.000203) | |
binary recursive 0.000000 0.000000 0.000000 ( 0.000334) | |
binary iterative 0.000000 0.000000 0.000000 ( 0.000258) |
def recursive_binary_search(arr, value, min, max) | |
mid = min + (max - min) / 2 | |
if arr[mid] == value | |
return mid | |
elsif min >= max | |
return nil | |
elsif arr[mid] > value | |
recursive_binary_search(arr, value, min, mid - 1) | |
elsif arr[mid] < value | |
recursive_binary_search(arr, value, mid + 1, max) | |
end | |
end | |
def iterative_binary_search(arr, value) | |
min = 0 | |
max = arr.length | |
while max >= min | |
mid = min + (max - min) / 2 | |
if arr[mid] == value | |
return mid | |
elsif arr[mid] > value | |
max = mid - 1 | |
elsif arr[mid] < value | |
min = mid + 1 | |
end | |
end | |
end | |
require 'benchmark' | |
arr = 100_000_000.times.map { Random.rand(1_000_000) } | |
arr.sort! | |
value = arr[Random.rand(arr.length)] | |
puts "Searching for #{value} in sorted array" | |
fail unless arr[arr.index(value)] == value | |
fail unless arr.bsearch { |v| v >= value } == value | |
fail unless arr[recursive_binary_search(arr, value, 0, arr.length)] == value | |
fail unless arr[iterative_binary_search(arr, value)] == value | |
Benchmark.bm(20) do |x| | |
x.report('linear') { 100.times { arr.index(value) } } | |
x.report('native binary') { 100.times { arr.bsearch {|v| v == value} } } | |
x.report('binary recursive') { 100.times { recursive_binary_search(arr, value, 0, arr.length) } } | |
x.report('binary iterative') { 100.times { iterative_binary_search(arr, value) } } | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment