--- title: "Bob’s Notebook: Binary Search" type: "article" slug: "bobs-notebook-19" url: "http://localhost/article/bobs-notebook-19/" markdown_url: "http://localhost/article/bobs-notebook-19.md" published_at: "2022-01-19T01:47:38+00:00" modified_at: "2026-07-02T11:31:55+00:00" featured_image: url: "http://localhost/wp-content/uploads/2022/04/20230809-041332.jpg" excerpt: "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…" category: - name: "Sinc-Link" slug: "sinc-link" taxonomy: "category" url: "http://localhost/category/periodicals/sinc-link/" post_tag: - name: "Best of Timex/Sinclair 2068 Articles and Documents" slug: "ts2068best" taxonomy: "post_tag" url: "http://localhost/tag/ts2068best/" - name: "TS 2068" slug: "ts2068" taxonomy: "post_tag" url: "http://localhost/tag/ts2068/" - name: "Type-in program" slug: "type-in-program" taxonomy: "post_tag" url: "http://localhost/tag/type-in-program/" model: - name: "Timex/Sinclair 2068" slug: "ts-2068" taxonomy: "model" url: "http://localhost/model/ts-2068/" indiv: - name: "Bob Mitchell" slug: "bob-mitchell" taxonomy: "indiv" url: "http://localhost/indiv/bob-mitchell/" publication: "Sinc-Link" publication_r: id: 10240 title: "Sinc-Link" type: "periodical" url: "http://localhost/periodical/sinc-link/" authors: "Bob Mitchell" authors_r: - name: "Bob Mitchell" slug: "bob-mitchell" taxonomy: "indiv" url: "http://localhost/indiv/bob-mitchell/" volume: "4" issue: "1" issues_articles: - id: 38193 title: "Sinc-Link v4 n1" type: "issue" url: "http://localhost/issue/sinc-link-v4-n1/" pages: "8" pubdate: "January/February 1986" archive_link: false --- # Bob’s Notebook: Binary Search This is program is based on one by [John Gilbert](http://localhost/indiv/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. ## Source Code ``` 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)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)