binary_search_exercise.rb

# This was during the whole only 10% of programmers can write a binary search on their first try
# Ars Technica had a thread on the issue at http://arstechnica.com/civis/viewtopic.php?f=20&t=1106689

def search(number, array=[])
  return false if array.empty?
  
  middle = array.length/2
  number_at_middle = array[middle]
  return true if number_at_middle==number
  return false if array.length==1 && !(number_at_middle==number) # program failed before, it was missing this line

  if number_at_middle < number
    return search(number, array[(middle+1)..(array.length-1)])
  else
    return search(number, array[0..(middle-1)])
  end
end

evens_odd_length = [2,4,6,8,10,12,14,16,18]
evens_even_length = [2,4,6,8,10,12,14,16,18, 20]

odds_odd_length = [1,3,5,7,9,11,15,17, 19]
odds_even_length = [1,3,5,7,9,11,15,17]

puts "\nSearching for even numbers is the even arrays"
puts "Searching for 6 in evens_odd_length: #{search(6, evens_odd_length)}"
puts "Searching for 6 in evens_even_length: #{search(6, evens_even_length)}"
puts "Searching for 12 in evens_odd_length: #{search(12, evens_odd_length)}"
puts "Searching for 12 in evens_even_length: #{search(12, evens_even_length)}"
puts "Searching for 16 in evens_odd_length: #{search(16, evens_odd_length)}"
puts "Searching for 16 in evens_even_length: #{search(16, evens_even_length)}"

puts "\nSearching for even numbers is the odd arrays"
puts "Searching for 6 in odds_odd_length: #{search(6, odds_odd_length)}"
puts "Searching for 6 in odds_even_length: #{search(6, odds_even_length)}"
puts "Searching for 12 in odds_odd_length: #{search(12, odds_odd_length)}"
puts "Searching for 12 in odds_even_length: #{search(12, odds_even_length)}"
puts "Searching for 16 in odds_odd_length: #{search(16, odds_odd_length)}"
puts "Searching for 16 in odds_even_length: #{search(16, odds_even_length)}"

puts "\nSearching for odd numbers is the even arrays"
puts "Searching for 1 in evens_odd_length: #{search(1, evens_odd_length)}"
puts "Searching for 1 in evens_even_length: #{search(1, evens_even_length)}"
puts "Searching for 9 in evens_odd_length: #{search(9, evens_odd_length)}"
puts "Searching for 9 in evens_even_length: #{search(9, evens_even_length)}"
puts "Searching for 17 in evens_odd_length: #{search(17, evens_odd_length)}"
puts "Searching for 17 in evens_even_length: #{search(17, evens_even_length)}"

puts "\nSearching for odd numbers is the odd arrays"
puts "Searching for 1 in odds_odd_length: #{search(1, odds_odd_length)}"
puts "Searching for 1 in odds_even_length: #{search(1, odds_even_length)}"
puts "Searching for 9 in odds_odd_length: #{search(9, odds_odd_length)}"
puts "Searching for 9 in odds_even_length: #{search(9, odds_even_length)}"
puts "Searching for 17 in odds_odd_length: #{search(17, odds_odd_length)}"
puts "Searching for 17 in odds_even_length: #{search(17, odds_even_length)}"