27 lines
750 B
Mojo
27 lines
750 B
Mojo
# probe: binary search over a sorted list, found and not found
|
|
# status: the expected output is Programming+'s interpreter's prediction; corpus.py verify confirms or refutes it on godbolt
|
|
# expect-stdout: 7 3
|
|
# expect-stdout: 1 0
|
|
# expect-stdout: 13 6
|
|
# expect-stdout: 4 -1
|
|
# expect-stdout: 0 -1
|
|
# expect-stdout: 14 -1
|
|
def search(xs: List[Int], target: Int) -> Int:
|
|
var lo = 0
|
|
var hi = len(xs) - 1
|
|
while lo <= hi:
|
|
var mid = (lo + hi) // 2
|
|
if xs[mid] == target:
|
|
return mid
|
|
elif xs[mid] < target:
|
|
lo = mid + 1
|
|
else:
|
|
hi = mid - 1
|
|
return -1
|
|
|
|
|
|
def main():
|
|
var xs: List[Int] = [1, 3, 5, 7, 9, 11, 13]
|
|
for t in [7, 1, 13, 4, 0, 14]:
|
|
print(t, search(xs, t))
|