Ruby linear search and binary search performance testing

results.txt

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)

search.rb

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