Page 80 - DCAP507_SYSTEM_SOFTWARE

System Software

Notes Linear search is demonstrated in Figure 5.1.
Figure 5.1: Sample Linear Search Program

LA 4, SYMTBL Start of table
LOOP CLC 0(8,4), SYMBOL Compare symbols
BE SYMFOUND Equal
A 4,= F'14' Move to next symbol
C 4, LAST Are we at end of table
BNE LOOP Loop back if not
NOTFOUND (Symbol not found)


SYMFOUND (Symbol found)


SYMBOL DS CL14 Symbol to be searched for, character string of length 14
SYMTBL DS 100CL14 Symbol table space (14 bytes per entry)
LAST DC A(-----) Address of current end of symbol table

This kind of linear search procedure is okay for short tables and has an ease in the procedure, but
it can be very slow for long tables. It is analogous to searching for a word in a dictionary whose
contents are not in an ordered manner. It would give slight relieve to recognize that on an
average, you only have to look out for half of the dictionary.

Did u know? Linear search is also known as sequential search as it compares the consecutive
elements of the specified set by means of the search key.

Self Assessment

Fill in the blanks:
1. Linear search method accesses table in which the items have not been ………………… .
2. ………………… process can be very slow for long tables.
3. Linear search is also known as ………………… search as it compares the consecutive
elements of the specified set by means of the search key.
4. A specified keyword can be searched by comparing every ………………… in the table
with the specified keyword.

5.2 Binary Searching

Another relatively simple method of accessing a table is the binary search method. The entries
in the table are stored in alphabetically or numerically increasing order.
The drawback of sequential search can be eliminated if it becomes possible to eliminate large
portions of the list from consideration in subsequent iterations. Binary search requires sorted
data to operate on. In this method, search begins by examining the records in the middle of file
rather than the one at one of the ends as in sequential search.

Let us assume that file being searched is sorted on increasing value of key. Based on the result of
the comparison with the middle key, Km, following conclusions can be drawn.

74 LOVELY PROFESSIONAL UNIVERSITY