% 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