34 lines
1 KiB
Text
34 lines
1 KiB
Text
type BinarySearch:Recursive
|
|
fun binarySearch = int by List values, int value
|
|
fun recurse = int by int low, int high
|
|
if high < low do return -1 end
|
|
int mid = low + (high - low) / 2
|
|
return when(values[mid] > value,
|
|
recurse(low, mid - 1),
|
|
when(values[mid] < value,
|
|
recurse(mid + 1, high),
|
|
mid))
|
|
end
|
|
return recurse(0, values.length - 1)
|
|
end
|
|
type BinarySearch:Iterative
|
|
fun binarySearch = int by List values, int value
|
|
int low = 0
|
|
int high = values.length - 1
|
|
while low <= high
|
|
int mid = low + (high - low) / 2
|
|
if values[mid] > value do high = mid - 1
|
|
else if values[mid] < value do low = mid + 1
|
|
else do return mid
|
|
end
|
|
end
|
|
return -1
|
|
end
|
|
List values = int[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]
|
|
List matches = int[24324, 32, 78, 287, 0, 42, 45, 99999]
|
|
for each int match in matches
|
|
writeLine("index is: " +
|
|
BinarySearch:Recursive.binarySearch(values, match) + ", " +
|
|
BinarySearch:Iterative.binarySearch(values, match))
|
|
end
|