Algorithms

binary-search.rb

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