Page 81 - DCAP507_SYSTEM_SOFTWARE

Unit 5: Table Processing: Searching

 If K < Km then if the record being searched for is in the file, it must be in the lower Notes
numbered half of the file.

 If K = Km then the middle record is the one being searched for.
 If K > Km then if the record being searched for is in the file it must be in the higher
numbered half of the file.
A search for a particular item which contains key value resembles the search for a name in a
telephone directory. The approximate middle entry of the table is located, and its key value is
examined. If its value is too high, then the key value of the middle entry of the first half of the
table is examined and the procedure is repeated on the first half until the required item is found.
If the value is too low, then the key of middle entry of the second half of the table is tried and the
procedure is repeated on the second half.

Example: As an example of binary search, let us consider a table of 15 items as shown in
Figure 5.2.
For example, suppose that we are looking for item IF (for ease the values are not displayed). We
first compare IF with the middle item LO and discover that IF must be in the top half of the table;
a second comparison with the middle item in this half of the table, FU shows IF to be in the
second quarter; a third comparison with W shows IF to be in the third eighth of the table (that is,
between items 4 and 6). and a final comparison is done with the item in position 5. A comparison
failure on the fourth probe would have discovered that the item is not present in the table.
This kind of bracketing technique of looking for a table should be clear in principle even though
its accomplishment may be a little more complex. We call this as a binary search or a logarithmic
search, you should know that as the effective table is halved on each probe, a maximum of about
log (N) probes is needed to search it.
2
On comparing the times of the linear search with those of the binary search where A and B are
overhead times connected with each table probe, we get:
T (tin) = A*N
T (bin) = B* log N;
2
As the binary search is more complex, the constant B can be considerably larger than A.

Figure 5.2: Illustration of Binary Search

Number Symbol Probe 1 Probe 2 Probe 3 Probe 4
1 AL
2 EX
3 FN

4 FU
IF > FU
5 IF
IF = IF
6 IW IF < IW
7 LE
8 LO IF < LO
9 NC
10 OP
11 OR
12 RD
13 RN
14 TE
15 TI

LOVELY PROFESSIONAL UNIVERSITY 75