binary search

binary_search

def binary_search(array, key, from = nil, to = nil)
  return nil if array.empty?

  to ||= array.size - 1
  from ||= 0
  return nil if from > to or ( from == to and array[from] != key )
  mid_idx = (from + to) / 2

  if key == array[mid_idx]
    return mid_idx
  elsif key < array[mid_idx]
    binary_search(array, key, from, mid_idx - 1)
  else
    binary_search(array, key, mid_idx + 1, to)
  end
end

def no_recursive_binary_search(array, key)
  return nil if array.empty?
  from = 0
  to = array.size - 1
  loop do
    return nil if from > to or ( from == to and array[from] != key )
    mid_idx = (from + to) / 2
    mid_value = array[mid_idx]
    if mid_value == key
      return mid_idx
    elsif key < mid_value
      to = mid_idx - 1
    else
      from = mid_idx + 1
    end
  end
  return nil
end

puts binary_search((1..15).to_a, 8) == 7
puts binary_search((1..15).to_a, 1) == 0
puts binary_search((1..15).to_a, 14) == 13
puts binary_search([2,3,8,15], 8) == 2
puts binary_search((1..15).to_a, 16) == nil


puts no_recursive_binary_search((1..15).to_a, 8) == 7
puts no_recursive_binary_search((1..15).to_a, 1) == 0
puts no_recursive_binary_search((1..15).to_a, 14) == 13
puts no_recursive_binary_search([2,3,8,15], 8) == 2
puts no_recursive_binary_search((1..15).to_a, 16) == nil