TAOCP 6.1 Exercise 22

Let $R_1,\dots,R_N$ be the file and let $d(K_i,A)$ be the distance from record $R_i$ to the given argument $A$.

taocpmathematicsalgorithmsvolume-3medium

Section 6.1: Sequential Searching

Exercise 22. [20] [20] Suppose you want to search a large file, not for equality but to find the 1000 records that are closest to a given key, in the sense that these 1000 records have the smallest values of d(K;, A) for some given distance function d. What data structure is most appropriate for such a sequential search?

Attempt the end, and never stand to doubt; Nothing’s so hard, but search will find it out., ROBERT HERRICK, Seeke and finde (1648)

6.2.1 SEARCHING AN ORDERED TABLE A409

6.2. SEARCHING BY COMPARISON OF KEYS

IN THIS SECTION we shall discuss search methods that are based on a linear ordering of the keys, such as alphabetic order or numeric order. After comparing the given argument K to a key K; in the table, the search continues in three different ways, depending on whether K < Kk;, K = K;, or K > K;. The sequential search methods of Section 6.1 were essentially limited to a two-way decision (K = K; versus K # K;), but if we free ourselves from the restriction of sequential access we are able to make effective use of an order relation.

6.2.1. Searching an Ordered Table

What would you do if someone handed you a large telephone directory and told you to find the name of the person whose number is 795-6841? There is no better way to tackle this problem than to use the sequential methods of Section 6.1. (Well, you might try to dial the number and talk to the person who answers; or you might know how to obtain a special directory that is sorted by number instead of by name.) The point is that it is much easier to find an entry by the party’s name, instead of by number, although the telephone directory contains all the information necessary in both cases. When a large file must be searched, sequential scanning is almost out of the question, but an ordering relation simplifies the job enormously.

With so many sorting methods at our disposal (Chapter 5), we will have little difficulty rearranging a file into order so that it may be searched conveniently. Of course, if we need to search the table only once, a sequential search would be faster than to do a complete sort of the file; but if we need to make repeated searches in the same file, we are better off having it in order. Therefore in this section we shall concentrate on methods that are appropriate for searching a table whose keys satisfy

Ki, < Ko <---< Ky,

assuming that we can easily access the key in any given position. After comparing K to K; in such a table, we have either

eK <K; [R;, Ri41,..., Rw are eliminated from consideration]; or ek =K; [the search is done]; or eK>K; [Ri, Ro,...,R; are eliminated from consideration].

In each of these three cases, substantial progress has been made, unless 7 is near one of the ends of the table; this is why the ordering leads to an efficient algorithm.

Binary search. Perhaps the first such method that suggests itself is to start by comparing K to the middle key in the table; the result of this probe tells which half of the table should be searched next, and the same procedure can be used again, comparing K to the middle key of the selected half, etc. After at most about lg N comparisons, we will have found the key or we will have established

A410 SEARCHING 6.2.1

B1. Initialize

B2. Get midpoint

u<l

FAILURE

B5. Adjust l

B4. Adjust u

SUCCESS

Fig. 3. Binary search.

that it is not present. This procedure is sometimes known as “logarithmic search” or “bisection,” but it is most commonly called binary search.

Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky, and many good programmers have done it wrong the first few times they tried. One of the most popular correct forms of the algorithm makes use of two pointers, | and u, that indicate the current lower and upper limits for the search, as follows:

Algorithm B (Binary search). Given a table of records Ri, Ro, ..., Rx whose keys are in increasing order Ky < Ky <---: < Ky, this algorithm searches for a given argument K.

B1. [Initialize.] Set 1<- 1,u + N.

B2. [Get midpoint.] (At this point we know that if K is in the table, it satisfies Ki < K < K,. A more precise statement of the situation appears in exercise 1 below.) If u < J, the algorithm terminates unsuccessfully. Otherwise, set i < | (d +u)/ 2|, the approximate midpoint of the relevant table area.

B3. [Compare.] If K < Kj, go to B4; if kK > K;, go to Bd; and if K = K;, the algorithm terminates successfully.

BA. [Adjust u.] Set uw << i, 1 and return to B2. BB. [Adjust J.] Set 1<- i+ 1 and return to B2. J

Figure 4 illustrates two cases of this binary search algorithm: first to search for the argument 653, which is present in the table, and then to search for 400, which is absent. The brackets indicate | and u, and the underlined key represents K;. In both examples the search terminates after making four comparisons.

6.2.1 SEARCHING AN ORDERED TABLE All

a) Searching for 653:

[061 087 154 170 275 426 503 509 512 612 653 677 703 765 897 908] 061 087 154 170 275 426 503 509 [512 612 653 677 703 765 897 908] 061 087 154 170 275 426 503 509 [512 612 653] 677 703 765 897 908 061 087 154 170 275 426 503 509 512 612 [653] 677 703 765 897 908

b) Searching for 400:

[061 087 154 170 275 426 503 509 512 612 653 677 703 765 897 908] [061 087 154 170 275 426 503] 509 512 612 653 677 703 765 897 908 061 087 154 170[275 426 503] 509 512 612 653 677 703 765 897 908 061 087 154 170 [275] 426 503 509 512 612 653 677 703 765 897 908 061 087 154 170 275] [426 503 509 512 612 653 677 703 765 897 908

Fig. 4. Examples of binary search. Program B (Binary search). As in the programs of Section 6.1, we assume

here that K; is a full-word key appearing in location KEY +7. The following code uses rll = 1, rl2 = u, rI3 =i.

01 START ENT1 1 1 Bl. Initialize. | < 1.

02 ENT2 N 1 uN.

03 JMP 2F 1 To B2.

04 5H JE SUCCESS Cl Jump if K = K;.

05 ENT1 1,3 C1, S Bb. Adjustl. lHi+l. 06 2H ENTA 0,1 C+1, -, S B2. Get midpoint.

07 INCA 0,2 C+1-S rA¢el+u.

08 SRB 1 C+1-S rA¢ |rA/2|. (rX changes too.) 09 STA TEMP C+1-S

10 CMP1 TEMP C+1-S

11 JG FAILURE C+4+1-S Jumpifu<l.

12 LD3 TEMP C 2 < midpoint.

13 3H LDA K C B3. Compare.

U4 CMPA KEY,3 C

15 JGE 5B C Jump if K > K;.

16 ENT2 -1,3 C2 B4. Adjust u. u<-i-1. 17 JMP 2B C2 To B2. J

This procedure doesn’t blend with MIX quite as smoothly as the other algorithms we have seen, because MIX does not allow much arithmetic in index registers. The running time is (18C, 105 + 12)u, where C = C1+4 C2 is the number of comparisons made (the number of times step B3 is performed), and S' = [outcome is successful]. The operation on line 08 of this program is “shift right binary 1,” which is legitimate only on binary versions of MIX; for general byte size, this instruction should be replaced by “MUL =1//2+1=”, increasing the running time to (26C', 185 + 20)u.

A tree representation. In order to really understand what is happening in Algorithm B, our best bet is to think of the procedure as a binary decision tree, as shown in Fig. 5 for the case N = 16.

A412 SEARCHING 6.2.1

Fig. 5. A comparison tree that corresponds to binary search when N = 16.

When N is 16, the first comparison made by the algorithm is K : Kg; this is represented by the root node in the figure. Then if K < Kg, the algorithm follows the left subtree, comparing K to Ky; similarly if K > Kg, the right subtree is used. An unsuccessful search will lead to one of the external square nodes numbered [0] through [N]; for example, we reach node [6] if and only if Ke < K < Kz.

The binary tree corresponding to a binary search on N records can be constructed as follows: If N = 0, the tree is simply [0]. Otherwise the root

node is CiN/21),

the left subtree is the corresponding binary tree with [N/2], 1 nodes, and the right subtree is the corresponding binary tree with |N/2| nodes and with all node numbers increased by [N/2].

In an analogous fashion, any algorithm for searching an ordered table of length N by means of comparisons can be represented as an N-node binary tree in which the nodes are labeled with the numbers 1 to N (unless the algorithm makes redundant comparisons). Conversely, any binary tree corresponds to a valid method for searching an ordered table; we simply label the nodes

Ml OF @® &@. Bw @® WM &

in symmetric order, from left to right.

If the search argument input to Algorithm B is Kyo, the algorithm makes the comparisons K > Kg, K < Ky2, K = Kyo. This corresponds to the path from the root to in Fig. 5. Similarly, the behavior of Algorithm B on other keys corresponds to the other paths leading from the root of the tree. The method of constructing the binary trees corresponding to Algorithm B therefore makes it easy to prove the following result by induction on N:

Theorem B. If2*~! < N < 2*, a successful search using Algorithm B requires (min 1, max k) comparisons. If N = 2*, 1, an unsuccessful search requires

6.2.1 SEARCHING AN ORDERED TABLE A413

k comparisons; and if 2k-! < N < 2*, 1, an unsuccessful search requires either k, 1 ork comparisons. |

Further analysis of binary search. (Nonmathematical readers should skip to Eq. (4).) The tree representation shows us also how to compute the average number of comparisons in a simple way. Let Cy be the average number of comparisons in a successful search, assuming that each of the N keys is an equally likely argument; and let Ci, be the average number of comparisons in an unsuccessful search, assuming that each of the N + 1 intervals between and outside the extreme values of the keys is equally likely. Then we have

internal path length of tree external path length of tree N , N+1 , by the definition of internal and external path length. We saw in Eq. 2.3.4.5-(3)

that the external path length is always 2N more than the internal path length. Hence there is a rather unexpected relationship between C'y and Cy:

Cy = (1+ 5 )ch-1. (2)

This formula, which is due to T. N. Hibbard [JACM 9 (1962), 16-17], holds for all search methods that correspond to binary trees; in other words, it holds for all methods that are based on nonredundant comparisons. The variance of successful-search comparisons can also be expressed in terms of the corresponding variance for unsuccessful searches (see exercise 25).

From the formulas above we can see that the “best” way to search by comparisons is one whose tree has minimum external path length, over all binary trees with N internal nodes. Fortunately it can be proved that Algorithm B is optimum in this sense, for all N; for we have seen (exercise 5.3.1-20) that a binary tree has minimum path length if and only if its external nodes all occur on at most two adjacent levels. It follows that the external path length of the tree corresponding to Algorithm B is

(N + 1)([lg NJ +2), 208 NJ+1 (3)

(See Eq. 5.3.1-(34).) From this formula and (2) we can compute the exact

average number of comparisons, assuming that all search arguments are equally

probable.

N=12 3 4 5 6 7 8 9 10 11 12 18 #14 #15 += «16 _ 1 72 L 92 93 95 97 9 1 2 3 4 6

Cn=1 15 15 2 26 26 23 22 25 2755 3 37 3 377 3 3a

_ 2 2 54 96 2 94 6 8 910 912 gl4 2 Cy=113 2 22 25 22 3 35 355 347 3i5 359 37 335 4 4G

Cyn =1+

Ch =

In general, if k = |lg N|, we have Cy =k+1-(2"t!-k-2)/N =lgN-1+€+(k+2)/N, Cy =k+2, 2**1/(N +1) =lIg(N+1)+e

where 0 < €,¢’ < 0.0861; see Eq. 5.3.1-(35).

(4)

Verified: yes
Solve time: 1m31s

Solution

Let $R_1,\dots,R_N$ be the file and let $d(K_i,A)$ be the distance from record $R_i$ to the given argument $A$. The task is to select the $1000$ records whose distances are smallest among the values $d(K_i,A)$.

A sequential scan must examine each record at least once, since no ordering information about the values $d(K_i,A)$ is available a priori. During the scan, the problem reduces to maintaining the current set of the $1000$ smallest distances seen so far.

Let $M=1000$. Maintain a collection $H$ of at most $M$ records, organized as a max-heap keyed by $d(K_i,A)$. The root of $H$ is always the largest distance among the current candidates in $H$, so it represents the worst element of the current best set.

The algorithm proceeds by initializing $H$ with the first $M$ records and building a max-heap in linear time by the standard heap construction method. For each subsequent record $R_i$ with distance $x=d(K_i,A)$, compare $x$ with the key at the root of $H$. If $x$ is greater than or equal to the root key, the record cannot belong to the $M$ closest and is discarded. If $x$ is smaller than the root key, the root element is removed and $R_i$ is inserted into $H$, restoring the heap property.

Each replacement preserves the invariant that $H$ contains exactly the $M$ smallest distances among the records processed so far, since every element not in $H$ is greater than or equal to the current maximum of $H$. The final heap therefore contains exactly the $1000$ records with smallest values of $d(K_i,A)$.

The heap representation is appropriate because it supports extraction of the current worst candidate and insertion of a new candidate in time proportional to $\log M$, while $M$ remains fixed and much smaller than $N$. This yields an optimal sequential-search structure for the stated task under a single pass constraint, since every record must be examined and each must be compared at least once to determine whether it can enter the candidate set.

This completes the construction. ∎