Page 82 - DCAP507_SYSTEM_SOFTWARE

System Software

Notes Let us now see an example of binary search program as below.

Example: Figure 5.3 illustrates an example of binary search program. As the binary
process frequently divides by 2, for effectiveness and simplicity we suppose table size is a power
of 2. This condition is simply achieved by just adding enough “dummy” entries to the end of the
table (such as entries for the symbol ZZZZ ZZZZ).

Figure 5.3: Sample Binary Search Program

L 5,SIZE Set table size ( 2N * 14 bytes)
SRL 5,1 Divide by 2 by shifting
LR 6,5 Copy into register 6
LOOP SRL 6,1 Divide table size in half again
LA 4,SYMTBL(5) Set address of table entry
CLC 0(8,4),SYMBOL Compare with symbol
BE FOUND Symbols match, entry found
BH TOOHIGH SYMTBL entry > SYMBOL
TOOLOW AR 5,6 Move higher in table
B TESTEND
TOOHIGH SR 5,6 Move lower in table
TESTEND LTR 6,6 Test if remaining size is 0
BNZ LOOP No, look at next entry
NOTFOUND (Symbol not found)


FOUND (Symbol found)

Self Assessment

Fill in the blanks:

5. In ………………… searching, the entries in the table are stored in alphabetically or
numerically increasing order.
6. Binary search requires ………………… data to operate on.

7. In binary search method, search begins by examining the records in the middle of file
rather than the one at one of the ends as in ………………… search.
8. A search for a particular item which contains key value resembles the search for a
………………… in a telephone directory.
9. In binary search, an estimated ………………… entry of the table is located, and its key
value is examined.
10. Binary search is also known as ………………… search.
11. As the effective table is halved on each probe, a maximum of about ………………… probes
is needed to search it.

76 LOVELY PROFESSIONAL UNIVERSITY