Bob’s Notebook: Binary Search

This is program is based on one by John Gilbert published in Timex Sinclair User VoL. 1 #4.

Compared to the slower serial search often used in BASIC programs, the binary method is quite fast, doing its job in about one tenth of the time. The reason is that while the serial method looks at every record in a file, the binary does not.

First, all records must be sorted alphabetically (or numerically) for the binary method to work; meaning sorted according to the field to be searched on.

Here is how it works: (numbers in brackets refer to line numbers)

1. A search data string (a$) is entered. This may be a word or words or part of a word or a number [2220]
2. The start of the field being searched is placed in variable ss. [2230]
3. Variable s takes on the value of the half-way point. [2350]
4. With the pass counter (p)=0 the record at the half way point is examined for a match and if found, then the record is printed [2400]; the pass counter incremented [2420]; variable s1 used to store the initial value of s [2340] and s incremented [2480].
5. If a match is not found then the record is examined to see if it is higher or lower than a$. If lower, the record will be taken as the end of the file and the other half cut away [2380]; if higher, the record will be the start of the file [2370]. We now have the new value for s which is already in the middle of the already halved list.
6. The search continued upward (alphabetically) untill s>bb when the search reverses direction downward ending when s1=aa [2500]; printing the record in the downward direction takes place [2510] and s1 is decremented [2530].
7. When records are printed, they will not be in strict alphabetical order; this could be corrected at the expense of time and memory.

Variables Used

• aa = start search
• bb = end search (n set by user)
• p = pass counter
• s1 = temporary storage for s
• a$ = search data string
• s = search limit half-way point
• r$ = data file being searched (may be changed throughout to suit user’s needs)
• n = number of records being searched (set by user or user program)
• ss = start of field used for search; now set at 1 but can be changed to suit user needs
• pz = limits search if no record found.

N.B. If any of these variables clash with those in your program, change them accordingly. Also, you may with to renumber this program to suit your needs.

 2200 REM BINARY SEARCH
 2210 LET pz=0: LET aa=1: LET bb=n+1: LET p=0: LET s1=1
 2220 INPUT ("enter search data")' LINE a$
 2230 LET ss=1
 2240 CLS
 2250 PRINT #1;AT 0,0;"Searching for ";a$
 2340 LET s=INT ((bb-aa))/2+.5)
 2350 GO TO 2390
 2360 IF s>bb THEN GO TO 2540
 2370 IF r$(s,ss to ss+LEN a$-1)>a$ THEN LET s=INT ((bb-aa)/2+.5)
 2380 IF r$(s,ss to ss+LEN a$-1)<a$ then LET s=int((bb-aa)/2+.5+aa
 2385 IF p=0 and pz=10 THEN CLS: BEEP 1,-20: PRINT AT 10,0;"NO RECORD FOUND WITH"'a$: PAUSE 120: RETURN
 2390 IF p>0 and r$(s1)=r$(s) THEN GO TO 2500
 2400 IF r$(s,ss to ss+LEN a$-1)=a$ THEN PRINT r$(s)
 2420 IF r$(s,ss to ss+LEN a$-1)=a$ THEN LET p=p+1
 2430 IF p=1 AND r$(s,ss to ss+LEN a$-1)=a$ THEN LET s1=s
 2440 IF r$(s,ss to ss+LEN a$-1)=a$ THEN GO TO 2480
 2450 IF r$(s,ss to ss+LEN a$-1)>a$ THEN LET bb=s
 2460 IF r$(s,ss to ss+LEN a$-1)<a$ THEN LET aa=s
 2470 LET pz=pz+1: GO TO 2360
 2480 LET s=s+1
 2490 GO TO 2360
 2500 IF s1<=aa THEN GO TO 2550
 2510 IF r$(s,ss to ss+LEN a$-1)=a$ THEN PRINT r$(s1-1)
 2530 LET s1=s1-1
 2550 RETURN