binarysearch.a68

STRING success message   = "Found!";
STRING not found message = "Not found";
STRING out of bounds     = "Value is out of bounds";


PROC binary search = ([] INT row, INT looking for) INT:
BEGIN #  Binary search over a sorted array in Algol 68  #

    INT end     := ELEMS row;
    INT start   := 1;
    INT middle  := (end - start) % 2;

    IF looking for > row[UPB row] OR looking for < row[LWB row]
    THEN
        print((out of bounds, new line));
        stop
    FI;

    IF (middle) < 1
    THEN
        IF looking for = row[end] OR looking for = row[start]
        THEN
            print((success message, new line));
            stop
        ELSE
            print((not found message, new line));
            stop
        FI
    FI;

    IF looking for = row[middle]
    THEN
        print((success message, new line));
        stop
    ELIF looking for < row[middle]
    THEN 
        binary search(row[1 .. middle-1], looking for)
    ELSE
        binary search(row[middle+1 .. ELEMS row], looking for)
    FI;
    1
END;


BEGIN
    [] INT row = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 23);
    binary search(row, read int)
END