Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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
You can’t perform that action at this time.