binary_search and find_index

sort.rb

require 'benchmark'
arr = [0, 5, 13, 13, 30, 42, 52, 70, 85, 96, 103, 111, 116, 127, 130, 143, 150, 150, 161, 175, 207, 210, 218, 246, 257, 257, 263, 280, 304, 310, 326, 327, 332, 346, 360, 371, 374, 378, 406, 407, 407, 408, 428, 431, 437, 442, 445, 479, 489, 491, 505, 517, 520, 536, 548, 598, 602, 605, 618, 642, 649, 654, 659, 662, 677, 678, 682, 689, 695, 696, 697, 701, 711, 717, 727, 737, 745, 749, 754, 757, 770, 786, 802, 805, 814, 832, 840, 850, 853, 854, 888, 894, 904, 913, 913, 945, 962, 964, 972, 998]

def binary_search(arr, element)
  l = 0
  r = arr.length - 1

  while l <= r

    mid = l + ((r - l) / 2)
    if arr[mid] == element
      return mid
    elsif arr[mid] > element
      r = mid - 1
    else
      l = mid + 1
    end
  end

  '404!'
end

# p binary_search(arr, 666)
# p arr.bsearch_index{|x| x >= 371}

def sorted_array(length)
  arr = Array.new(length) { rand(10000) }
  arr.sort
end

a1 = sorted_array 10
a2 = sorted_array 10_000
a3 = sorted_array 1_000_000

Benchmark.bm do |x|
  x.report('#binary_search with 10-element array') do
    binary_search a1, 7899
  end
  x.report('#binary_search with 10000-element array') do
    binary_search a2, 7899
  end
  x.report('#binary_search with 1000000-element array') do
    binary_search a3, 7899
  end
  x.report('#bsearch with 10-element array') do
    a1.bsearch_index { |x| x >= 7899 }
  end
  x.report('#bsearch with 10000-element array') do
    a2.bsearch_index { |x| x >= 7899 }
  end
  x.report('#bsearch with 1000000-element array') do
    a3.bsearch_index { |x| x >= 7899 }
  end
  x.report('#find_index with 1000000-element array') do
    a3.find_index 7899
  end
end