Page 85 - DCAP507_SYSTEM_SOFTWARE

Unit 5: Table Processing: Searching

Notes
Figure 5.4: Example of Open Addressing
Position Item Probes to find Probes to find not
0 1 1
1 01 1 6
2 19,02* 2 5
3 02 1 4
4 21 1 3
5 05 2
6 1
7 1
8 1
9 26.09* 1 7
10 27,09* 1 6
11 09,11* 3 5
12 11 2 4
13 13 1 3
14 31 1 2
15 1
16 16 1 1
16 54

Task Make distinction between ‘Random entry with replacement’ and ‘Random entry
without replacement’ techniques.

Self Assessment

Fill in the blanks:
12. Hash searching is also termed as ………………… Searching.
13. In random entry with replacement technique, the random numbers generated are
independent and it is perfectly possible to probe the same position ………………… .
14. In case of …………………, any effort to probe the same position two times is avoided.
15. In case of …………………, 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.4 Summary

 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.
 Linear search is as, in the average case, one-half of the items in the search space will be
scrutinized before a match is located.

 In binary searching, the entries in the table are stored in alphabetically or numerically
increasing order.

 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.

LOVELY PROFESSIONAL UNIVERSITY 79