31 lines
600 B
Text
31 lines
600 B
Text
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}" }
|