48 lines
1.5 KiB
Plaintext
48 lines
1.5 KiB
Plaintext
% Binary search in an array
|
|
% If the item is found, returns `true' and the index;
|
|
% if the item is not found, returns `false' and the leftmost insertion point
|
|
% The datatype must support the < and > operators.
|
|
binary_search = proc [T: type] (a: array[T], val: T) returns (bool, int)
|
|
where T has lt: proctype (T,T) returns (bool),
|
|
T has gt: proctype (T,T) returns (bool)
|
|
low: int := array[T]$low(a)
|
|
high: int := array[T]$high(a)
|
|
|
|
while low <= high do
|
|
mid: int := low + (high - low) / 2
|
|
if a[mid] > val then
|
|
high := mid - 1
|
|
elseif a[mid] < val then
|
|
low := mid + 1
|
|
else
|
|
return (true, mid)
|
|
end
|
|
end
|
|
return (false, low)
|
|
end binary_search
|
|
|
|
% Test the binary search on an array
|
|
start_up = proc ()
|
|
po: stream := stream$primary_output()
|
|
|
|
% primes up to 20 (note that arrays are 1-indexed by default)
|
|
primes: array[int] := array[int]$[2,3,5,7,11,13,17,19]
|
|
|
|
% binary search for each number from 1 to 20
|
|
for n: int in int$from_to(1,20) do
|
|
i: int
|
|
found: bool
|
|
found, i := binary_search[int](primes, n)
|
|
|
|
if found then
|
|
stream$putl(po, int$unparse(n)
|
|
|| " found at location "
|
|
|| int$unparse(i));
|
|
else
|
|
stream$putl(po, int$unparse(n)
|
|
|| " not found, would be inserted at location "
|
|
|| int$unparse(i));
|
|
end
|
|
end
|
|
end start_up
|