TAOCP 6.1 Exercise 4

Section 6.1: Sequential Searching

Exercise 4. ▶ [17] Does the idea of Algorithm Q carry over from subscript notation to linked-memory notation? (See exercise 2.)

Verified: no
Solve time: 56s

Solution

Yes, the sentinel technique of Algorithm Q adapts directly to linked-memory representation.

Assume the linked-memory conventions of Exercise 2: each record has fields $\mathit{KEY}$, $\mathit{INFO}$, and $\mathit{LINK}$; $\mathit{FIRST}$ points to the first record; the last record has $\mathit{LINK} = \Lambda$ (null). We introduce a permanent dummy record $D$ with $\mathit{LINK}(D) = \Lambda$ and arrange that the last real record (if any) points to $D$; if the table is empty, $\mathit{FIRST} = D$.

Before a search for argument $K$, we set $\mathit{KEY}(D) \leftarrow K$. The search then proceeds as follows:

Algorithm Q (Linked memory).

1. Set $P \leftarrow \mathit{FIRST}$.
2. If $\mathit{KEY}(P) = K$, go to step 4.
3. Set $P \leftarrow \mathit{LINK}(P)$ and return to step 2.
4. If $P = D$, terminate unsuccessfully; otherwise terminate successfully with the desired record at $P$.

Correctness. The loop (steps 2-3) examines successive records until a key equal to $K$ is found. Because $\mathit{KEY}(D) = K$, the loop is guaranteed to terminate, either at a genuine record or at $D$. Step 4 distinguishes these two cases. The empty table ($\mathit{FIRST} = D$) is handled correctly: step 2 immediately finds $\mathit{KEY}(D) = K$ and step 4 reports failure.

Efficiency. The inner loop contains only one test (the key comparison), eliminating the end-of-list check required in the linked-memory version of Algorithm S (Exercise 2). The number of key comparisons $C$ is the index of the first matching record, or $N+1$ if the search is unsuccessful, exactly as in the array version.

This completes the proof. ∎