29 lines
586 B
Ruby
29 lines
586 B
Ruby
class Array
|
|
def binary_search_iterative(val)
|
|
low, high = 0, length - 1
|
|
while low <= high
|
|
mid = (low + high) >> 1
|
|
case val <=> self[mid]
|
|
when 1
|
|
low = mid + 1
|
|
when -1
|
|
high = mid - 1
|
|
else
|
|
return mid
|
|
end
|
|
end
|
|
nil
|
|
end
|
|
end
|
|
|
|
ary = [0,1,4,5,6,7,8,9,12,26,45,67,78,90,98,123,211,234,456,769,865,2345,3215,14345,24324]
|
|
|
|
[0,42,45,24324,99999].each do |val|
|
|
i = ary.binary_search_iterative(val)
|
|
if i
|
|
puts "found #{val} at index #{i}: #{ary[i]}"
|
|
else
|
|
puts "#{val} not found in array"
|
|
end
|
|
end
|