� > SEARCH
� Jonathan Evans July 1991
?� Searches for words in an order list using binary chopping

	�init
(�search("S")
2�search("B")
<�
F
P
��init
Zwmax=1600:swds = 6
d"� words$(wmax),searchwd$(swds)
n� i = 1 � swds
x� searchwd$(i)
�� i
�(�read_text_file("WORDS",words$(),nl)
�8� ;nl;" alphabetically ordered words read from file"
��
�:� "and","each","largely","pointless","testing","which"
�
�,��read_text_file(file$,text$(),� nlines)
� � Reads text file into array
�0� Line length must not exceed 255 characters
�4� nlines returns number of lines in file (array)
�� line,line$,file
�file=�(file$)
�
line=0

ȕ � �#file

line$=�#file

line+=1

"text$(line)=line$

,�

6nlines=line

@�

J

T��search(s$)

^� w,pos,t1

hȎ s$ �

r	� "S"

|� '"SERIAL SEARCH DEMO"

�	� "B"

�� '"BINARY SEARCH DEMO"

��

�� w = 1 � swds

�=� '"Searching for """;searchwd$(w);""" among ";nl" words"

�t1=�

�Ȏ s$ �

�8� "S":pos = �serial_search(searchwd$(w),words$(),nl)

�8� "B":pos = �binary_search(searchwd$(w),words$(),nl)

��

�t2 = (�-t1)/100

�Ȏ pos �

�� 0
#� "Not found in ";t2;" seconds"

3� "Found at position ";pos;" in ";t2;" seconds"
&�
0� REPEAT UNTIL GET
:� w
D�
N
X"ݤserial_search(w$,words$(),n)
b
� w,found
lfound = �: w = 0
v�
�	w +=1
� � w$ = words$(w) � found = �
�� found � w = n
�� � found � = 0 � = w
�
�"ݤbinary_search(w$,words$(),n)
�3� pos,m,wp$,off,p,hipos,lopos,lp2,found,missing
�%missing = �:found = �:m = n:off=0
�%pos = m � 2: lopos = 1: hipos = n
��
�wp$ = words$(pos)
�lastpos = pos
�� w$ = wp$ �

found = �
�
� w$ < wp$ �
 &� search word alphabetically lower
*hipos = pos
4m = pos - lopos
>pos = m � 2 + off
H�
R'� search word alphabetically higher
\lopos = pos
f
off = pos
pm = hipos - pos
zpos = m � 2 +off
��
��
�!� lp2 = lastpos � missing = �
�lp2 = lastpos
�� PRINT lastpos, wp$
�� found � missing
�� � found � = 0 � = lastpos
�
�
�
�

00000000  0d 00 0a 0e f4 20 3e 20  53 45 41 52 43 48 0d 00  |..... > SEARCH..|
00000010  0b 1e f4 20 4a 6f 6e 61  74 68 61 6e 20 45 76 61  |... Jonathan Eva|
00000020  6e 73 20 4a 75 6c 79 20  31 39 39 31 0d 00 0c 3f  |ns July 1991...?|
00000030  f4 20 53 65 61 72 63 68  65 73 20 66 6f 72 20 77  |. Searches for w|
00000040  6f 72 64 73 20 69 6e 20  61 6e 20 6f 72 64 65 72  |ords in an order|
00000050  20 6c 69 73 74 20 75 73  69 6e 67 20 62 69 6e 61  | list using bina|
00000060  72 79 20 63 68 6f 70 70  69 6e 67 0d 00 14 04 0d  |ry chopping.....|
00000070  00 1e 09 f2 69 6e 69 74  0d 00 28 10 f2 73 65 61  |....init..(..sea|
00000080  72 63 68 28 22 53 22 29  0d 00 32 10 f2 73 65 61  |rch("S")..2..sea|
00000090  72 63 68 28 22 42 22 29  0d 00 3c 05 e0 0d 00 46  |rch("B")..<....F|
000000a0  04 0d 00 50 0a dd f2 69  6e 69 74 0d 00 5a 16 77  |...P...init..Z.w|
000000b0  6d 61 78 3d 31 36 30 30  3a 73 77 64 73 20 3d 20  |max=1600:swds = |
000000c0  36 0d 00 64 22 de 20 77  6f 72 64 73 24 28 77 6d  |6..d". words$(wm|
000000d0  61 78 29 2c 73 65 61 72  63 68 77 64 24 28 73 77  |ax),searchwd$(sw|
000000e0  64 73 29 0d 00 6e 12 e3  20 69 20 3d 20 31 20 b8  |ds)..n.. i = 1 .|
000000f0  20 73 77 64 73 0d 00 78  12 f3 20 73 65 61 72 63  | swds..x.. searc|
00000100  68 77 64 24 28 69 29 0d  00 82 07 ed 20 69 0d 00  |hwd$(i)..... i..|
00000110  8c 28 f2 72 65 61 64 5f  74 65 78 74 5f 66 69 6c  |.(.read_text_fil|
00000120  65 28 22 57 4f 52 44 53  22 2c 77 6f 72 64 73 24  |e("WORDS",words$|
00000130  28 29 2c 6e 6c 29 0d 00  96 38 f1 20 3b 6e 6c 3b  |(),nl)...8. ;nl;|
00000140  22 20 61 6c 70 68 61 62  65 74 69 63 61 6c 6c 79  |" alphabetically|
00000150  20 6f 72 64 65 72 65 64  20 77 6f 72 64 73 20 72  | ordered words r|
00000160  65 61 64 20 66 72 6f 6d  20 66 69 6c 65 22 0d 00  |ead from file"..|
00000170  a0 05 e1 0d 00 aa 3a dc  20 22 61 6e 64 22 2c 22  |......:. "and","|
00000180  65 61 63 68 22 2c 22 6c  61 72 67 65 6c 79 22 2c  |each","largely",|
00000190  22 70 6f 69 6e 74 6c 65  73 73 22 2c 22 74 65 73  |"pointless","tes|
000001a0  74 69 6e 67 22 2c 22 77  68 69 63 68 22 0d 00 b4  |ting","which"...|
000001b0  04 0d 00 be 2c dd f2 72  65 61 64 5f 74 65 78 74  |....,..read_text|
000001c0  5f 66 69 6c 65 28 66 69  6c 65 24 2c 74 65 78 74  |_file(file$,text|
000001d0  24 28 29 2c f8 20 6e 6c  69 6e 65 73 29 0d 00 c8  |$(),. nlines)...|
000001e0  20 f4 20 52 65 61 64 73  20 74 65 78 74 20 66 69  | . Reads text fi|
000001f0  6c 65 20 69 6e 74 6f 20  61 72 72 61 79 0d 00 d2  |le into array...|
00000200  30 f4 20 4c 69 6e 65 20  6c 65 6e 67 74 68 20 6d  |0. Line length m|
00000210  75 73 74 20 6e 6f 74 20  65 78 63 65 65 64 20 32  |ust not exceed 2|
00000220  35 35 20 63 68 61 72 61  63 74 65 72 73 0d 00 dc  |55 characters...|
00000230  34 f4 20 6e 6c 69 6e 65  73 20 72 65 74 75 72 6e  |4. nlines return|
00000240  73 20 6e 75 6d 62 65 72  20 6f 66 20 6c 69 6e 65  |s number of line|
00000250  73 20 69 6e 20 66 69 6c  65 20 28 61 72 72 61 79  |s in file (array|
00000260  29 0d 00 e6 15 ea 20 6c  69 6e 65 2c 6c 69 6e 65  |)..... line,line|
00000270  24 2c 66 69 6c 65 0d 00  f0 11 66 69 6c 65 3d 8e  |$,file....file=.|
00000280  28 66 69 6c 65 24 29 0d  00 fa 0a 6c 69 6e 65 3d  |(file$)....line=|
00000290  30 0d 01 04 0f c8 95 20  ac 20 c5 23 66 69 6c 65  |0...... . .#file|
000002a0  0d 01 0e 10 6c 69 6e 65  24 3d be 23 66 69 6c 65  |....line$=.#file|
000002b0  0d 01 18 0b 6c 69 6e 65  2b 3d 31 0d 01 22 15 74  |....line+=1..".t|
000002c0  65 78 74 24 28 6c 69 6e  65 29 3d 6c 69 6e 65 24  |ext$(line)=line$|
000002d0  0d 01 2c 05 ce 0d 01 36  0f 6e 6c 69 6e 65 73 3d  |..,....6.nlines=|
000002e0  6c 69 6e 65 0d 01 40 05  e1 0d 01 4a 04 0d 01 54  |line..@....J...T|
000002f0  10 dd f2 73 65 61 72 63  68 28 73 24 29 0d 01 5e  |...search(s$)..^|
00000300  0e ea 20 77 2c 70 6f 73  2c 74 31 0d 01 68 0b c8  |.. w,pos,t1..h..|
00000310  8e 20 73 24 20 ca 0d 01  72 09 c9 20 22 53 22 0d  |. s$ ...r.. "S".|
00000320  01 7c 1b f1 20 27 22 53  45 52 49 41 4c 20 53 45  |.|.. '"SERIAL SE|
00000330  41 52 43 48 20 44 45 4d  4f 22 0d 01 86 09 c9 20  |ARCH DEMO"..... |
00000340  22 42 22 0d 01 90 1b f1  20 27 22 42 49 4e 41 52  |"B"..... '"BINAR|
00000350  59 20 53 45 41 52 43 48  20 44 45 4d 4f 22 0d 01  |Y SEARCH DEMO"..|
00000360  9a 05 cb 0d 01 a4 12 e3  20 77 20 3d 20 31 20 b8  |........ w = 1 .|
00000370  20 73 77 64 73 0d 01 ae  3d f1 20 27 22 53 65 61  | swds...=. '"Sea|
00000380  72 63 68 69 6e 67 20 66  6f 72 20 22 22 22 3b 73  |rching for """;s|
00000390  65 61 72 63 68 77 64 24  28 77 29 3b 22 22 22 20  |earchwd$(w);""" |
000003a0  61 6d 6f 6e 67 20 22 3b  6e 6c 22 20 77 6f 72 64  |among ";nl" word|
000003b0  73 22 0d 01 b8 08 74 31  3d 91 0d 01 c2 0b c8 8e  |s"....t1=.......|
000003c0  20 73 24 20 ca 0d 01 cc  38 c9 20 22 53 22 3a 70  | s$ ....8. "S":p|
000003d0  6f 73 20 3d 20 a4 73 65  72 69 61 6c 5f 73 65 61  |os = .serial_sea|
000003e0  72 63 68 28 73 65 61 72  63 68 77 64 24 28 77 29  |rch(searchwd$(w)|
000003f0  2c 77 6f 72 64 73 24 28  29 2c 6e 6c 29 0d 01 d6  |,words$(),nl)...|
00000400  38 c9 20 22 42 22 3a 70  6f 73 20 3d 20 a4 62 69  |8. "B":pos = .bi|
00000410  6e 61 72 79 5f 73 65 61  72 63 68 28 73 65 61 72  |nary_search(sear|
00000420  63 68 77 64 24 28 77 29  2c 77 6f 72 64 73 24 28  |chwd$(w),words$(|
00000430  29 2c 6e 6c 29 0d 01 e0  05 cb 0d 01 ea 13 74 32  |),nl).........t2|
00000440  20 3d 20 28 91 2d 74 31  29 2f 31 30 30 0d 01 f4  | = (.-t1)/100...|
00000450  0c c8 8e 20 70 6f 73 20  ca 0d 01 fe 07 c9 20 30  |... pos ...... 0|
00000460  0d 02 08 23 f1 20 22 4e  6f 74 20 66 6f 75 6e 64  |...#. "Not found|
00000470  20 69 6e 20 22 3b 74 32  3b 22 20 73 65 63 6f 6e  | in ";t2;" secon|
00000480  64 73 22 0d 02 12 05 7f  0d 02 1c 33 f1 20 22 46  |ds"........3. "F|
00000490  6f 75 6e 64 20 61 74 20  70 6f 73 69 74 69 6f 6e  |ound at position|
000004a0  20 22 3b 70 6f 73 3b 22  20 69 6e 20 22 3b 74 32  | ";pos;" in ";t2|
000004b0  3b 22 20 73 65 63 6f 6e  64 73 22 0d 02 26 05 cb  |;" seconds"..&..|
000004c0  0d 02 30 16 f4 20 52 45  50 45 41 54 20 55 4e 54  |..0.. REPEAT UNT|
000004d0  49 4c 20 47 45 54 0d 02  3a 07 ed 20 77 0d 02 44  |IL GET..:.. w..D|
000004e0  05 e1 0d 02 4e 04 0d 02  58 22 dd a4 73 65 72 69  |....N...X"..seri|
000004f0  61 6c 5f 73 65 61 72 63  68 28 77 24 2c 77 6f 72  |al_search(w$,wor|
00000500  64 73 24 28 29 2c 6e 29  0d 02 62 0d ea 20 77 2c  |ds$(),n)..b.. w,|
00000510  66 6f 75 6e 64 0d 02 6c  14 66 6f 75 6e 64 20 3d  |found..l.found =|
00000520  20 a3 3a 20 77 20 3d 20  30 0d 02 76 05 f5 0d 02  | .: w = 0..v....|
00000530  80 09 77 20 2b 3d 31 0d  02 8a 20 e7 20 77 24 20  |..w +=1... . w$ |
00000540  3d 20 77 6f 72 64 73 24  28 77 29 20 8c 20 66 6f  |= words$(w) . fo|
00000550  75 6e 64 20 3d 20 b9 0d  02 94 13 fd 20 66 6f 75  |und = ...... fou|
00000560  6e 64 20 84 20 77 20 3d  20 6e 0d 02 9e 19 e7 20  |nd . w = n..... |
00000570  ac 20 66 6f 75 6e 64 20  8c 20 3d 20 30 20 8b 20  |. found . = 0 . |
00000580  3d 20 77 0d 02 a8 04 0d  02 b2 22 dd a4 62 69 6e  |= w......."..bin|
00000590  61 72 79 5f 73 65 61 72  63 68 28 77 24 2c 77 6f  |ary_search(w$,wo|
000005a0  72 64 73 24 28 29 2c 6e  29 0d 02 bc 33 ea 20 70  |rds$(),n)...3. p|
000005b0  6f 73 2c 6d 2c 77 70 24  2c 6f 66 66 2c 70 2c 68  |os,m,wp$,off,p,h|
000005c0  69 70 6f 73 2c 6c 6f 70  6f 73 2c 6c 70 32 2c 66  |ipos,lopos,lp2,f|
000005d0  6f 75 6e 64 2c 6d 69 73  73 69 6e 67 0d 02 c6 25  |ound,missing...%|
000005e0  6d 69 73 73 69 6e 67 20  3d 20 a3 3a 66 6f 75 6e  |missing = .:foun|
000005f0  64 20 3d 20 a3 3a 6d 20  3d 20 6e 3a 6f 66 66 3d  |d = .:m = n:off=|
00000600  30 0d 02 d0 25 70 6f 73  20 3d 20 6d 20 81 20 32  |0...%pos = m . 2|
00000610  3a 20 6c 6f 70 6f 73 20  3d 20 31 3a 20 68 69 70  |: lopos = 1: hip|
00000620  6f 73 20 3d 20 6e 0d 02  da 05 f5 0d 02 e4 15 77  |os = n.........w|
00000630  70 24 20 3d 20 77 6f 72  64 73 24 28 70 6f 73 29  |p$ = words$(pos)|
00000640  0d 02 ee 11 6c 61 73 74  70 6f 73 20 3d 20 70 6f  |....lastpos = po|
00000650  73 0d 02 f8 10 e7 20 77  24 20 3d 20 77 70 24 20  |s..... w$ = wp$ |
00000660  8c 0d 03 02 0d 66 6f 75  6e 64 20 3d 20 b9 0d 03  |.....found = ...|
00000670  0c 05 cc 0d 03 16 10 e7  20 77 24 20 3c 20 77 70  |........ w$ < wp|
00000680  24 20 8c 0d 03 20 26 f4  20 73 65 61 72 63 68 20  |$ ... &. search |
00000690  77 6f 72 64 20 61 6c 70  68 61 62 65 74 69 63 61  |word alphabetica|
000006a0  6c 6c 79 20 6c 6f 77 65  72 0d 03 2a 0f 68 69 70  |lly lower..*.hip|
000006b0  6f 73 20 3d 20 70 6f 73  0d 03 34 13 6d 20 3d 20  |os = pos..4.m = |
000006c0  70 6f 73 20 2d 20 6c 6f  70 6f 73 0d 03 3e 15 70  |pos - lopos..>.p|
000006d0  6f 73 20 3d 20 6d 20 81  20 32 20 2b 20 6f 66 66  |os = m . 2 + off|
000006e0  0d 03 48 05 cc 0d 03 52  27 f4 20 73 65 61 72 63  |..H....R'. searc|
000006f0  68 20 77 6f 72 64 20 61  6c 70 68 61 62 65 74 69  |h word alphabeti|
00000700  63 61 6c 6c 79 20 68 69  67 68 65 72 0d 03 5c 0f  |cally higher..\.|
00000710  6c 6f 70 6f 73 20 3d 20  70 6f 73 0d 03 66 0d 6f  |lopos = pos..f.o|
00000720  66 66 20 3d 20 70 6f 73  0d 03 70 13 6d 20 3d 20  |ff = pos..p.m = |
00000730  68 69 70 6f 73 20 2d 20  70 6f 73 0d 03 7a 14 70  |hipos - pos..z.p|
00000740  6f 73 20 3d 20 6d 20 81  20 32 20 2b 6f 66 66 0d  |os = m . 2 +off.|
00000750  03 84 05 cd 0d 03 8e 05  cd 0d 03 98 21 e7 20 6c  |............!. l|
00000760  70 32 20 3d 20 6c 61 73  74 70 6f 73 20 8c 20 6d  |p2 = lastpos . m|
00000770  69 73 73 69 6e 67 20 3d  20 b9 0d 03 a2 11 6c 70  |issing = .....lp|
00000780  32 20 3d 20 6c 61 73 74  70 6f 73 0d 03 ac 18 f4  |2 = lastpos.....|
00000790  20 50 52 49 4e 54 20 6c  61 73 74 70 6f 73 2c 20  | PRINT lastpos, |
000007a0  77 70 24 0d 03 b6 15 fd  20 66 6f 75 6e 64 20 84  |wp$..... found .|
000007b0  20 6d 69 73 73 69 6e 67  0d 03 c0 1f e7 20 ac 20  | missing..... . |
000007c0  66 6f 75 6e 64 20 8c 20  3d 20 30 20 8b 20 3d 20  |found . = 0 . = |
000007d0  6c 61 73 74 70 6f 73 0d  03 ca 04 0d 03 d4 04 0d  |lastpos.........|
000007e0  03 de 04 0d ff                                    |.....|
000007e5