#* http://rosettacode.org/wiki/Binary_search
  Basic binary search
*#

binary_search = { search_array, value, low, high |
  true? high < low
    { null }
    {
      mid = ((low + high) / 2).to_i
      true? search_array[mid] > value
        { binary_search search_array, value, low, mid - 1 }
        { true? search_array[mid] < value
          { binary_search search_array, value, mid + 1, high }
          { mid }
        }
    }
}

#Populate array
numbers = 1000.of { random 1000 }

#Sort the array
numbers.sort!

#Find a number
x = random 1000

p "Looking for #{x}"

index = binary_search numbers, x, 0, numbers.length - 1

null? index
  { p "Not found" }
  { p "Found at index: #{index}" }