BEGIN


    INTEGER PROCEDURE BINARYSEARCHREC(A, LVALUE);
        INTEGER ARRAY A;
        INTEGER LVALUE; ! VALUE IS A KEY WORD ;
    BEGIN

        INTEGER PROCEDURE SEARCH(LOW, HIGH);
            INTEGER LOW, HIGH;
        BEGIN
            INTEGER MID;
            ! INVARIANTS: VALUE > A[I] FOR ALL I < LOW
                          VALUE < A[I] FOR ALL I > HIGH ;
            MID := (LOW + HIGH) // 2;
            SEARCH := IF HIGH < LOW THEN -LOW - 1
                 ELSE IF A(MID) > LVALUE THEN SEARCH(LOW, MID-1)
                 ELSE IF A(MID) < LVALUE THEN SEARCH(MID+1, HIGH)
                 ELSE MID;
        END SEARCH;

        BINARYSEARCHREC := SEARCH(LOWERBOUND(A, 1), UPPERBOUND(A, 1));
    END BINARYSEARCHREC;


    INTEGER PROCEDURE BINARYSEARCH(A, LVALUE);
        INTEGER ARRAY A;
        INTEGER LVALUE; ! VALUE IS A KEY WORD ;
    BEGIN
        INTEGER LOW, HIGH, MID;
        BOOLEAN FOUND;

        LOW := LOWERBOUND(A, 1);
        HIGH := UPPERBOUND(A, 1);
        WHILE NOT FOUND AND LOW <= HIGH DO BEGIN
            ! INVARIANTS: LVALUE > A(I) FOR ALL I < LOW
                          LVALUE < A(I) FOR ALL I > HIGH ;
            MID := (LOW + HIGH) // 2;
            IF A(MID) > LVALUE THEN
                HIGH := MID - 1
            ELSE IF A(MID) < LVALUE THEN
                LOW := MID + 1
            ELSE
                FOUND := TRUE;
        END;
        ! LVALUE WOULD BE INSERTED AT INDEX "LOW" ;
        BINARYSEARCH := IF FOUND THEN MID ELSE -LOW - 1;
    END BINARYSEARCH;


    COMMENT ** CAUTION ** ONLY WORKS FOR ARRAY LOWER BOUND=0;
    INTEGER ARRAY HAYSTACK(0:9);
    INTEGER I, J, K, NEEDLE;

    OUTTEXT("ARRAY = (");
    I := LOWERBOUND(HAYSTACK, 1);
    FOR J := 1, 6, 17, 29, 45, 78, 79, 87, 95, 100 DO BEGIN
        HAYSTACK(I) := J;
        OUTINT(HAYSTACK(I), 0);
        IF I < UPPERBOUND(HAYSTACK, 1) THEN OUTTEXT(", ");
        I := I + 1;
    END;
    OUTTEXT(")");
    OUTIMAGE;
    OUTIMAGE;

    FOR NEEDLE:= 0, 1, 7, 17, 95, 99, 100, 101 DO BEGIN

        OUTTEXT("LOOKUP RECURSIV ");
        OUTINT(NEEDLE, 3);
        OUTTEXT(" ... INDEX = ");
        K := BINARYSEARCHREC(HAYSTACK, NEEDLE);
        OUTINT(K, 3);
        IF K < 0 THEN OUTTEXT(" NOT FOUND!");
        OUTIMAGE;

        OUTTEXT("LOOKUP ITERATIV ");
        OUTINT(NEEDLE, 3);
        OUTTEXT(" ... INDEX = ");
        K := BINARYSEARCH(HAYSTACK, NEEDLE);
        OUTINT(K, 3);
        IF K < 0 THEN OUTTEXT(" NOT FOUND!");
        OUTIMAGE;

        OUTIMAGE;
    END;

END