Page 79 - DCAP507_SYSTEM_SOFTWARE

Avinash Bhagat, Lovely Professional University Unit 5: Table Processing: Searching

Unit 5: Table Processing: Searching Notes

CONTENTS

Objectives
Introduction
5.1 Linear Search
5.2 Binary Searching
5.3 Hash Searching

5.4 Summary
5.5 Keywords
5.6 Review Questions

5.7 Further Readings
Objectives

After studying this unit, you will be able to:
 Understand the concept of Linear Search
 Illustrate Binary Search

 Discuss Hash Searching

Introduction

The difficulty of searching is as follows: specified a keyword, locate an entry in the table that
matches, and returns its value. The particular problems more than one entry with the similar
keyword, and no entry discovered need individual conduct relying on the function of the table.
For an assembler's symbol table, these particular cases match to multiply defined symbols and
undefined symbols.

5.1 Linear Search

Linear search is a simple searching method. This method accesses table in which the items have
not been ordered. One manner to search for a specified keyword is to compare every entry in the
table with the specified keyword.
As you can see in the figure 5.1, the symbols and values are accumulated in contiguous locations
in an array named SYMTBL and defined by a DS. The word LAST includes the location of the
current “end of table.”

The loop illustrated will match up the keyword (in the location SYMBOL) with each succeeding
item in the table. When a match is found, array named SYMFOUND is used to make exit; if no
match is discovered by the end of the table, then execution will move to location NOTFOUND.
Generally, we would search half the table, by means of a linear search, before locating an entry.
Thus, the average length of time to locate an entry is

N
T(avg) = [overhead associated with entry probe] 
2

LOVELY PROFESSIONAL UNIVERSITY 73