'===========================================================================
' Subject: BINARY SEARCH ROUTINE              Date: 11-02-96 (15:01)       
'  Author: Joe Caverly                        Code: QB, QBasic, PDS        
'  Origin: 74214.637@CompuServe.COM         Packet: BINARY.ABC
'===========================================================================
'  I looked through the ABC Text for a binary search routine, but found none. I
'have this very large text file that is downloaded from the Mainframe each day,
'which is presently at 151,000 records, and growing. Each record is 328
'characters wide. The file is sorted by a 7-character customer number. I needed a
'means of rapidly looking up a customer number. However, instead of reading this
'very large text file into a database, I figured there had to be a way to rapidly
'search the file as-is. The code below does just that.

CLS
DIM RecordIn AS STRING * 9
LET RecLen = 9
LET TEST = FREEFILE
OPEN "C:\SETUP\ADANUM.TXT" FOR BINARY AS #TEST LEN = RecLen
LET wsmin = 0
LET wsmax = (LOF(TEST) / RecLen) + 1
LET wsmaxptr = (wsmax * RecLen) + 1
LET wsKey$ = "1218537"
DO
  LET wsmid = wsmin + ((wsmax - wsmin) \ 2)
  LET wsptr = (wsmid * RecLen) + 1
  IF wsmin > wsmax THEN
    PRINT "Not Found!"
    PRINT "Near Record Number "; wsmid
    EXIT DO
  END IF
  GET #TEST, wsptr, RecordIn
  LET wsRecordIn$ = LEFT$(RecordIn, 7)
  SELECT CASE wsRecordIn$
    CASE IS = wsKey$
      PRINT wsRecordIn$ + " equals " + wsKey$
      EXIT DO
    CASE IS < wsKey$
      'What we want is in the upper half
      PRINT wsRecordIn$ + " Less Than " + wsKey$
      LET wsmin = wsmid + 1
    CASE IS > wsKey$
      'What we want is in the lower half
      PRINT wsRecordIn$ + " Greater Than " + wsKey$
      LET wsmax = wsmid - 1
  END SELECT
LOOP
CLOSE #TEST
PRINT "Done!"
END

'Please note that the above program works with a fixed-width file where each
'record is 9 characters wide (7 characters of data plus a carriage return and
'line feed). If you want to generate a file to test this program with, here's a
'small program that will do just that. The above program would need to be
'modified to accept a record that is 13 characters wide (11 characters of data
'plus a carriage return and line feed).

OPEN "c:\setup\test.dat" FOR OUTPUT AS #1
FOR cntr = 1 TO 151000
  PRINT #1, USING "Line ######"; cntr
NEXT cntr
CLOSE #1
PRINT "Done!"
END