Binary vs. Iterative search with a large data set

result

mercury:search-test robb$ ruby ./test.rb 
       user     system      total        real
Binary search:      0.000000   0.000000   0.000000 (  0.000016)
Iterative search:   0.000000   0.000000   0.000000 (  0.004715)

Binary search:      0.000000   0.000000   0.000000 (  0.000010)
Iterative search:   0.010000   0.000000   0.010000 (  0.006112)

Binary search:      0.000000   0.000000   0.000000 (  0.000016)
Iterative search:   0.010000   0.000000   0.010000 (  0.010991)

Binary search:      0.000000   0.000000   0.000000 (  0.000013)
Iterative search:   0.000000   0.000000   0.000000 (  0.004382)

Binary search:      0.000000   0.000000   0.000000 (  0.000013)
Iterative search:   0.010000   0.000000   0.010000 (  0.007773)

test.rb

require 'benchmark'

def binary_search(name, array)
  lower = 0
  upper = array.length - 1

  while lower <= upper
    mid = (lower + upper) / 2
    mid_name = array[mid]

    if name == mid_name
      return array[mid]
    elsif name < mid_name
      upper = mid - 1
    elsif name> mid_name
      lower = mid + 1
    end
  end

  return nil
end

def iterative_search(name, array)
  i = 0

  while i <= (array.length - 1)
    if array[i] == name
      return array[i]
    else
      i += 1
    end
  end

  return nil

end


# 100,000 Big random numbers in string form
array_to_search = (1..100_000)
  .map { |i| rand(100_000_000_000).to_s }
  .sort

# Run 5 trials
Benchmark.bm do |x|
  (1..5).each do
    number_to_find = array_to_search.sample  # Chosen at random
    x.report('Binary search:    ') { binary_search number_to_find, array_to_search }
    x.report('Iterative search: ') { iterative_search number_to_find, array_to_search }
    puts
  end
end