-
-
Save dansanderson/8a842f696c5df97e4d8a1074a7c82d58 to your computer and use it in GitHub Desktop.
Binary search through DATA statements, taking advantage of the data elements being of equal length and in a regular format. CBM BASIC 2.0 for the Commodore 64.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
30 read wc:ds=peek(66)*256+peek(65)+6 | |
40 wo$="aaaaa":gosub 1200:print wo$,r | |
41 wo$="aabaa":gosub 1200:print wo$,r | |
42 wo$="aabac":gosub 1200:print wo$,r | |
43 wo$="cabac":gosub 1200:print wo$,r | |
44 wo$="cdefg":gosub 1200:print wo$,r | |
45 wo$="babbb":gosub 1200:print wo$,r | |
46 wo$="ccccc":gosub 1200:print wo$,r | |
47 wo$="cczzz":gosub 1200:print wo$,r | |
999 end | |
1100 rem set w$ to the i-th word | |
1110 ia=ds+36*int(i/5)+(i-int(i/5)*5)*6 | |
1111 if i=int(i/5)*5 then ia=ia-6 | |
1120 poke 66,int(ia/256):poke 65,ia-(int(ia/256)*256) | |
1130 read w$ | |
1140 return | |
1200 rem find wo$ in data quickly | |
1201 rem r = result:-1 if found, 0 if not | |
1202 rem expects wc=word count, ds=addr of first word | |
1210 lo=0:hi=wc | |
1220 i=int((hi-lo)/2)+lo | |
1230 gosub 1100 | |
1240 if wo$=w$ then r=-1:return | |
1250 if wo$<w$ then 1270 | |
1260 if lo=i then r=0:return | |
1265 lo=i:goto 1220 | |
1270 if hi=i then r=0:return | |
1280 hi=i:goto 1220 | |
1999 data 30 | |
2000 data aaaaa,aabaa,abbba,abcba,abcde | |
2010 data baaab,babab,bbbbb,bbcbb,bcdef | |
2020 data cabac,cbabc,ccccc,cdedc,cdefg | |
2030 data dabac,dbabc,dcccc,ddedc,ddefg | |
2040 data eabac,ebabc,ecccc,ededc,edefg | |
2050 data fabac,fbabc,fcccc,fdedc,fdefg |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment