89 lines
2.5 KiB
Plaintext
89 lines
2.5 KiB
Plaintext
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
|