Here is an example of a binary array search, originally written for PB/DOS v 3.2 and only recently run under PB/DOS 3.5

A binary search requires the array to be sorted in key order; and the only "condition" you may search for is "Equal To" (i.e, you cannot use a binary search for "greater than"); this implementation requires that all array subscripts be not less than zero.

To convert to PB/Windows, the INCR and DECR statements in FUNCTION BinaryFind must be changed, as PB/Windows does not support the 'amount' parameter of the PB/DOS "INCR dataname [,amount]" statement.

-------------

Michael Mattias

Racine WI USA

[email protected]

A binary search requires the array to be sorted in key order; and the only "condition" you may search for is "Equal To" (i.e, you cannot use a binary search for "greater than"); this implementation requires that all array subscripts be not less than zero.

To convert to PB/Windows, the INCR and DECR statements in FUNCTION BinaryFind must be changed, as PB/Windows does not support the 'amount' parameter of the PB/DOS "INCR dataname [,amount]" statement.

Code:

$IF 0 4.22.97 File: Bisearch.bas Build a binary search with recursive algorithm Author: Michael Mattias Racine WI Placed in the public domain by the author 2.13.00 Requires: Sorted array 4.22.97 all I have is an idea. 5.10.97 This will be useful as a replacement for ARRAY SCAN, which is a sequential search (I think - no it has to be , since it works on unsorted arrays!) 2.13.00 Move to PB 3.5, comment $ENDIF $LIB ALL OFF $ERROR ALL ON DEFINT A-Z COLOR 7,1:CLS MAIN: FOR K = 100 TO 32000 STEP 499 IF INKEY$ = CHR$(27) THEN PRINT PRINT "Aborted.." EXIT FOR END IF LOCATE 5, 10 PRINT SPACE$(40) LOCATE 5,10 PRINT "ArrayElements=";USING$ ("##,###", K);SPACE$(02); " (Escape Exits)"; LET NoElements = K GOSUB BuildArray FOR L = LBOUND (Y()) TO UBOUND(Y()) Target = L ' PRINT USING$("####",Target); Found = BinaryFind (Y(),Target) IF Found <> Target THEN PRINT "Failed on Target=";Target;" with elements=";K J$=INPUT$(01) IF J$=CHR$(27) THEN END END IF NEXT L NEXT K END BuildArray: ' build a sorted array REDIM Y(NoElements) AS INTEGER FOR I = LBOUND (Y) TO UBOUND (Y) Y(I) = I NEXT I RETURN FUNCTION BinaryFind (X() AS INTEGER, T AS INTEGER) AS INTEGER ' Returns: Index of X() where X(n) = T, or -9999 if not found. ' Will not work if array indices are negative. LOCAL I&, Interval% ON LOCAL ERROR GOTO BiSearchError IF T > X(UBOUND(X())) OR T < X(LBOUND (X())) THEN FUNCTION = -9999: EXIT FUNCTION Let I& = (UBOUND (X) - LBOUND(X) + 1) \ 2 Let Interval% = I& \ 2 ' first pass DO IF X(I&) = T THEN FUNCTION=CINT(I&) EXIT FUNCTION END IF Interval% = Interval% \ 2 + Interval% MOD 2 IF X(I&) > T THEN DECR I&, Interval% ELSE INCR I&, Interval% END IF LOOP UNTIL Interval% = 0 FUNCTION = -9999 PRINT "NotFound" BiSearchResume: EXIT FUNCTION BiSearchError: PRINT "Error";ERR;" when elements="UBOUND(X())" and target="T" and I&="I& J$=INPUT$(01) RESUME BiSearchResume END FUNCTION

-------------

Michael Mattias

Racine WI USA

[email protected]

## Comment