Different binary search implementations in ruby with benchmarks.

binary_search.rb

# simple recursive algorithm
def binary_search_recursive(ary, value)
  return nil if ary.empty?
  pivot = ary.length / 2
  pivot_value = ary[pivot]
  if pivot_value < value
    binary_search_recursive(ary[(pivot + 1)..-1], value)
  elsif pivot_value == value
    return pivot
  else
    binary_search_recursive(ary[0...pivot], value)
  end
end

# loop version, to avoid 'stack level too deep' errors
def binary_search_loop(ary, value)
  while ary.length > 0
    pivot = ary.length / 2
    pivot_value = ary[pivot]
    if pivot_value < value
      ary = ary[(pivot + 1)..-1]
    elsif pivot_value == value
      return pivot
    else
      ary = ary[0...pivot]
    end
  end
end

# loop version that doesn't create new arrays, so should be faster
def binary_search_no_create_array(ary, value)
  start = 0
  finish = ary.length
  
  while (length = finish - start) > 0
    pivot = start + (length / 2)
    pivot_value = ary[pivot]
    if pivot_value < value
      start = pivot + 1
    elsif pivot_value == value
      break pivot
    else
      finish = pivot
    end
  end
end

require 'benchmark'

repeats = 10
array = (0..1_000).to_a
value = 499_999

Benchmark.bm(19) do |x|
  
  x.report("Array#index") do
    repeats.times do
      array.index(value)
    end
  end
  
  x.report("recursive") do
    repeats.times do
      binary_search_recursive(array, value)
    end
  end
  
  x.report("loop") do
    repeats.times do
      binary_search_loop(array, value)
    end
  end
  
  x.report("loop, no new arrays") do
    repeats.times do
      binary_search_no_create_array(array, value)
    end
  end
  
  x.report("#bsearch") do
    repeats.times do
      array.bsearch {|x| value <=> x}
    end
  end
  
end