34 lines
1.1 KiB
Plaintext
34 lines
1.1 KiB
Plaintext
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]
|
|
writeLine("recursive | iterative")
|
|
matches.list(<int match|writeLine(
|
|
(text!BinarySearch:Recursive.binarySearch(values, match)).padStart(9, " "), " | ",
|
|
(text!BinarySearch:Iterative.binarySearch(values, match)).padStart(9, " ")))
|