home *** CD-ROM | disk | FTP | other *** search
/ Programming Tool Box / SIMS_2.iso / bp_6_93 / bonus / winer / chap8-4.bas < prev    next >
BASIC Source File  |  1992-05-12  |  1KB  |  48 lines
  1. '*********** CHAP8-4.BAS - Binary search routine
  2.  
  3. 'Copyright (c) 1992 Ethan Winer
  4.  
  5. DEFINT A-Z
  6. DECLARE FUNCTION BinarySearch% (Array$(), Find$)
  7.  
  8. CLS
  9. PRINT "Creating test data..."
  10.  
  11. REDIM Array$(1 TO 1000)         'create a "sorted" array
  12. FOR X = 1 TO 1000
  13.   Array$(X) = "String " + RIGHT$("000" + LTRIM$(STR$(X)), 4)
  14. NEXT
  15.  
  16. PRINT "Searching array..."
  17.  
  18. FoundAt = BinarySearch%(Array$(), "String 0987")
  19. IF FoundAt >= 0 THEN
  20.   PRINT "Found at element"; FoundAt
  21. ELSE
  22.   PRINT "Not found"
  23. END IF
  24.  
  25. FUNCTION BinarySearch% (Array$(), Find$) STATIC
  26.  
  27. BinarySearch% = -1              'no matching element yet
  28. Min = LBOUND(Array$)            'start at first element
  29. Max = UBOUND(Array$)            'consider through last
  30.  
  31. DO
  32.   Try = (Max + Min) \ 2         'start testing in middle
  33.  
  34.   IF Array$(Try) = Find$ THEN   'found it!
  35.     BinarySearch% = Try         'return matching element
  36.     EXIT DO                     'all done
  37.   END IF
  38.  
  39.   IF Array$(Try) > Find$ THEN   'too high, cut in half
  40.     Max = Try - 1
  41.   ELSE
  42.     Min = Try + 1               'too low, cut other way
  43.   END IF
  44. LOOP WHILE Max >= Min
  45.  
  46.  
  47. END FUNCTION
  48.