 Web pdp-10.trailing-edge.com

Trailing-Edge - PDP-10 Archives - decuslib20-03 - decus/20-0078/libsim/lookup.sim
There is 1 other file named lookup.sim in the archive. Click here to see a list.
OPTIONS(/E/C/-A/-Q/-I/-D);
!     Procedure LOOKUP will perform a binary search for T in the
!     text array TA within the interval [LOW,HIGH].  The text
!     array contents must be sorted in ASCENDING order!  (I.e.
!     TA[J] < TA[J+1].  Use procedure SORTTA for sorting if
!     necessary.) If the text is found in TA the matching index I
!     will be returned (for which TA[I] = T) and LOOKUP will
!     return TRUE.  If the text is NOT found LOOKUP will return
!     FALSE and I will be either in the range [LOW,HIGH-1] in case
!     TA[I] > T > TA[I+1] or else I = HIGH if T > TA[HIGH] or I
!     = LOW-1 IF T < TA[LOW].  Author:  Mats Ohlin, FOA 1, S-104 50
!     STOCKHOLM 80, SWEDEN.
;
BOOLEAN PROCEDURE lookup(t,ta,low,high,i);  NAME i;  TEXT t;
TEXT ARRAY ta;   INTEGER low,high,i;

IF low <= high THEN
BEGIN   INTEGER j;

OPTIONS(/A); COMMENT START ARRAY BOUNDS CHECKING;
IF
ta[low] < t AND t < ta[high]
THEN
BEGIN ;
OPTIONS(/-A); COMMENT NO ARRAY BOUNDS CHECKING;
FOR j:= (low+high)//2 WHILE high > low + 1 DO
IF ta[j] > t THEN high:= j ELSE
IF ta[j] < t THEN low:= j ELSE
BEGIN   lookup:= TRUE;   GO TO out  END
END  inside range ELSE
IF ta[low] = t THEN
BEGIN   lookup:= TRUE;   j:= low END ELSE
IF ta[high] = t THEN
BEGIN   lookup:= TRUE;   j:= high END ELSE
IF ta[low] > t THEN j:= low - 1 ELSE
IF ta[high] < t THEN j:= high;

out:  i:= j

END of lookup;