TAOCP 5.5 Exercise 81

Section 5.5: Summary, History, and Bibliography

Exercise 81. [**] [Initialize.] Set «<< 1.

$2. [Compare.] If K = K;, the algorithm terminates successfully.

$3. [Advance.] Increase i by 1.

S4. [End of file?] If 7 < N, go back to $2. Otherwise the algorithm terminates

unsuccessfully. J

Notice that this algorithm can terminate in two different ways, successfully (having located the desired key) or unsuccessfully (having established that the given argument is not present in the table). The same will be true of most other algorithms in this chapter.

No S1. Initialize 53. Advance 84. End of file?

Yes SUCCESS FAILURE

Fig. 1. Sequential or “house-to-house” search.

Verified: yes
Solve time: 1m08s

At initialization $i \leftarrow 1$. Before each execution of step $S2$, the index $i$ satisfies $1 \le i \le N+1$ and every position $j$ with $1 \le j < i$ has already been examined with result $K_j \ne K$. This property holds initially because no indices are less than $1$, and it is preserved because step $S2$ checks $K_i$ and step $S3$ increases $i$ by $1$.

If at some stage step $S2$ finds $K_i = K$, the algorithm halts with success since the required key has been located. If no such index exists, then after repeated applications of step $S3$ the index becomes $i = N+1$. Step $S4$ then triggers termination with failure because all indices $1,2,\dots,N$ have been checked and none contains the key. Thus the algorithm terminates in exactly one of the two stated ways, and each termination case correctly reflects whether an index $i$ with $K_i = K$ exists. This completes the proof. ∎