Page 86 - DCAP507_SYSTEM_SOFTWARE

System Software

Notes  We call a binary search as logarithmic search also, as when the effective table is halved on
each probe, a maximum of about log (N) probes is needed to search it.
2
 In random entry with replacement technique, the random numbers generated are
independent and it is perfectly possible (but not likely) to probe the same position twice.
 In case of random entry without replacement, any effort to probe the same position two
times is avoided.
 In case of open addressing, if the first probe provides a position K and that position is
filled, then the next location K + 1 is probed, and so on in anticipation of a free position.

5.5 Keywords

Binary Search: In binary searching, the entries in the table are stored in alphabetically or
numerically increasing order.
Linear Search: In linear searching, to locate a given item, start your search at the beginning of
the data collection and persist to observe until you have either located the goal or exhausted the
search space.
Random Entry Searching: These kinds of search procedures may have to be utilized in combination
with a sort algorithm which orders the data and packs the data as well.

5.6 Review Questions

1. Illustrate the problem of searching in table processing.
2. Explain the concept of linear search with example.
3. What is binary searching? Illustrate the concept.
4. Give an example of linear search program and illustrate.
5. Give an example of a binary search program. Explain.

6. In binary search, search begins by examining the records in the middle of file rather than
the one at one of the ends as in sequential search. Comment.
7. Illustrate the process of hash searching with example.

8. What is open addressing? Illustrate the concept with example.
9. It is needless for the table to be ordered and packed to attain good speed in searching.
Comment.

10. Explain the concept of power residue method.

Answers: Self Assessment

1. ordered 2. Linear search
3. sequential 4. entry
5. binary 6. sorted

7. sequential 8. name
9. middle 10. logarithmic
11. log (N) 12. Random Entry
2

80 LOVELY PROFESSIONAL UNIVERSITY