'===========================================================================
' Subject: BINARY SEARCH                     Date: 10-25-99 (18:05)       
' Author:  Randall L. Glass                  Code: PB                     
' Origin:  rlglass@yahoo.com               Packet: PB.ABC
'===========================================================================
'----------------------------------------------------------------------------
'
'                                Binary Search
'                               BY Randall Glass
'                                Copyright 1999
'
'----------------------------------------------------------------------------
' FREEWARE
'
' You may use this as long as you give me credit somewhere in the documentation
'
' Email rlglass@yahoo.com
'
'--------------------------------------------------------------------------

dim varArray$(1 to 550)
open "pbcomand.dat" for input as #1

i% = 0

do
	incr i%
	input #1,VarArray$(i%)
Loop until eof(1)
close
total% = i%
array sort VarArray$(1) for total%
mtimer
k% = BinSearch (1,total%,"INSERT", VarArray$() )
m?? = Mtimer
print m??
stop

DEFINT A-Z

FUNCTION BinSearch (byval MinPos%,byval MaxPos%,Find$, AStringArray$()) Public
'MinPos% = start at first element
'MaxPos% = through last element
!       push DS
!       mov Cx,MinPos%
!       mov Dx,MaxPos%
TryAgain:
!       mov ax,cx        ;CX = Minpos%
!       add ax,dx        ;DX = MaxPos%
!       shr ax,1         ;ax = Try
!       mov Try,ax
'  Try = (MaxPos% + MinPos%) \ 2         'start testing in middle

  IF AStringArray$(Try) = Find$ THEN     'found it!
        BinSearch = Try
!       jmp JustDone
	'BiSearch = Try              'return matching element
'	EXIT LOOP                     'all done
  END IF

  IF AStringArray$(Try) > Find$ THEN     'too high, cut in half
	!      mov  dx,ax
      !      dec  dx
'     MaxPos% = Try - 1
  ELSE
      !  mov cx,ax
      !  Inc cx
'	MinPos% = Try + 1               'too low, cut other way
  END IF
!      cmp  dx,cx
!      jae   TryAgain
'if    MaxPos% >= MinPos%  then goto tryagain
JustDone:
!     Pop   DS
END FUNCTION
'-------------------------------------------------------------------------
$ALIAS
$CODE
$COM
$COM1
$COM2
$COMPILE
$CPU
$DEBUG
$DIM
$DYNAMIC
$ELSE
$ENDIF
$ERROR
$EVENT
$FLOAT
$HUGE
$IF
$INCLUDE
$INLINE
$LIB
$LINK
$LIST
$OPTIMIZE
$OPTION
$SEGMENT
$SOUND
$STACK
$STATIC
$STRING
ABS
ABSOLUTE
ACCESS
ALIAS
ALL
AND
ANY
APPEND
ARRAY
AS
ASC
ASCEND
ASCII
ASM
AT
ATN
ATTRIB
BASE
BCD
BEEP
BIN$
BINARY
BIT
BITS
BLOAD
BSAVE
BYTE
BYVAL
CALL
CASE
CBCD
CBYT
CCUR
CDBL
CDECL     
CDWD
CEIL
CEXT
CFIX
CHAIN
CHDIR
CHDRIVE
CHR$
CINT
CIRCLE
CLEAR
CLNG
CLOSE
CLS
CODEPTR
CODESEG
COLLATE
COLOR
COM
COMMAND$
COMMON
COS
CQUD
CSNG
CSRLIN
CURDIR$
CVB
CVBYT
CVD
CVDWD
CVE
CVF
CVI
CVL
CVMD
CVMS
CVQ
CVS
CVWRD
CWRD
DATA
DATE$
DECLARE
DECR
DEF
DEFBCD
DEFBYT
DEFCUR
DEFDBL
DEFDWD
DEFEXT
DEFFIX
DEFFLX
DEFINT
DEFLNG
DEFQUD
DEFSNG
DEFSTR
DEFWRD
DELAY
DELETE
DESCEND
DIM
DIR$
DO
DOUBLE
DRAW
DWORD
DYNAMIC
ELSE
ELSEIF
EMS
END
ENDMEM
ENVIRON
ENVIRON$
EOF
EQV
ERADR
ERASE
ERDEV
ERDEV$
ERL
ERR
ERROR
ERRTEST
EVENT
EXE
EXECUTE
EXIT
EXP
EXP10
EXP2
EXTERNAL
EXTRACT$
FAR
FIELD
FILEATTR
FILES
FIX
FIXDIGITS
FLEXCHR$
FLUSH
FN
FOR
FRAC
FRE
FREEFILE
FROM
FUNCTION
GET
GET$
GO
GOSUB
GOTO
HEX$
IF
IMP
IN
INCR
INKEY$
INLINE
INP
INPUT
INPUT$
INSERT
INSTAT
INSTR
INT
INTEGER
INTERRUPT
IOCTL
IOCTL$
IS
ISFALSE
ISTRUE
ITERATE
KEY
KILL
LBOUND
LCASE$
LEFT
LEFT$
LEN
LET
LINE
LIST
LOC
LOCAL
LOCATE
LOCK
LOF
LOG
LOG10
LOG2
LONG
LOOP
LPOS
LPRINT
LSET
LTRIM$
MAP
MAX
MAX$
MAX%
MEMPACK
MEMSET
MID$
MIN
MIN$
MIN%
MKB$
MKBYT$
MKD$
MKDIR
MKDWD$
MKE$
MKF$
MKI$
MKL$
MKMD$
MKMS$
MKQ$
MKS$
MKWRD$
MOD
MTIMER
MULTIPLEX
NAME
NEXT
NOT
OCT$
OFF
ON
OPEN
OPTION
OR
OUT
OUTPUT
PAINT
PALETTE
PBVBINBASE
PBVCPU
PBVCURSOR1
PBVCURSOR2
PBVCURSORVIS
PBVDEFSEG
PBVERR
PBVFIXDIGITS
PBVFLEXCHR
PBVHOST
PBVMINUSONE
PBVNPX
PBVONE
PBVREVISION
PBVREVLTR
PBVSCRNAPAGE
PBVSCRNBUFF
PBVSCRNCARD
PBVSCRNCOLS
PBVSCRNMODE
PBVSCRNPXLATTR
PBVSCRNROWS
PBVSCRNTXTATTR
PBVSCRNVPAGE
PBVSWITCH
PBVUSERAREA
PBVUSINGCHRS
PBVVTXTX1
PBVVTXTX2
PBVVTXTY1
PBVVTXTY2
PBVZERO
PEEK
PEEK$
PEEKI
PEEKL
PEN
PLAY
PMAP
POINT
POKE
POKE$
POKEI
POKEL
POPUP
POS
PRESET
PRINT
PRIVATE
PSET
PTR
PUBLIC
PUT
PUT$
QUIET
RANDOM
RANDOMIZE
READ
REDIM
REG
REM
REMOVE$
REPEAT$
REPLACE
RESET
RESTORE
RESUME
RETURN
RIGHT
RIGHT$
RMDIR
RND
ROTATE
ROUND
RSET
RTRIM$
RUN
SAVE
SCAN
SCREEN
SEEK
SEG
SELECT
SETMEM
SGN
SHARED
SHELL
SHIFT
SIGNED
SIN
SINGLE
SLEEP
SORT
SOUND
SPACE$
SPC
SQR
STATIC
STEP
STICK
STOP
STR$
STRIG
STRING
STRING$
STRPTR32
STRPTR
STRSEG
STUFF
SUB
SWAP
SYSTEM
TAB
TAGARRAY
TALLY
TAN
THEN
TIME$
TIMER
TO
TROFF
TRON
TYPE
UBOUND
UCASE
UCASE$
UEVENT
UNION
UNIT
UNLOCK
UNTIL
USING
USING$
USR
VAL
VARPTR
VARPTR$
VARSEG
VERIFY
VIEW
WAIT
WEND
WHILE
WIDTH
WINDOW
WITH
WORD
WRITE
XOR