TAOCP 6.2.1 Exercise 7
The flaw in the previous solution is that it replaces Algorithm U’s interval invariant with a “reachability” heuristic.
Section 6.2.1: Searching an Ordered Table
Exercise 7. [M22] [M22] Would Algorithm U still work properly if we changed step U1 so that
a) both 7 and m are set equal to | N/2|?
b) both i and m are set equal to [N/2]?
[Hint: Suppose the first step were “Set i ~, 0, m< N (or N +1), go to U4.”|
Verified: yes
Solve time: 3m04s
The flaw in the previous solution is that it replaces Algorithm U’s interval invariant with a “reachability” heuristic. A correct argument must reconstruct the invariant actually maintained by U1–U4 and show how the modified initialization affects its validity.
Correct invariant for Algorithm U
Algorithm U maintains an ordered table position within a single shrinking interval determined by two variables $i$ and $m$.
The intended invariant (as suggested by the hint “set $i \leftarrow 0$, $m \leftarrow N+1$, go to U4”) is:
$$ \text{If the key } K \text{ occurs at position } j,\quad i < j \le i+m $$
That is, the possible location of the key is always confined to a half-open interval of length $m$, whose left endpoint is $i$.
The updates in U3 and U4 preserve this structure by replacing $(i,m)$ with a new pair corresponding to either the left or right half of the current interval, always maintaining the form
$$ (i', m') \quad \text{with} \quad i' < j \le i' + m'. $$
Thus correctness depends critically on the initial condition that the interval $(i, i+m]$ covers the entire table:
$$ (0, N+1] \supseteq {1,\dots,N}. $$
Key observation
The invariant is not “the algorithm can reach all indices by displacement.”
It is:
The true position $j$, if it exists, must remain inside the maintained interval at every step.
If the initial interval does not cover ${1,\dots,N}$, correctness can fail immediately, because the algorithm never expands the interval again.
(a) $i \leftarrow \lfloor N/2 \rfloor,\quad m \leftarrow \lfloor N/2 \rfloor$
With this initialization, the initial interval becomes:
$$ (i, i+m] = \left(\left\lfloor \frac{N}{2} \right\rfloor,; \left\lfloor \frac{N}{2} \right\rfloor + \left\lfloor \frac{N}{2} \right\rfloor \right] $$
For simplicity, write $h = \lfloor N/2 \rfloor$. Then the interval is:
$$ (h, 2h] $$
Since $2h \le N$, this interval is contained in $(h, N]$. In particular, every index
$$ 1,2,\dots,h $$
is excluded from the initial search interval.
Why this breaks correctness
The updates in U3 and U4 only replace the current interval by a subinterval of the same form $(i', i'+m']$. In particular:
- the left endpoint $i$ is never moved leftward,
- the maintained interval always remains contained in the initial interval $(h,2h]$.
Hence every key located at any position $j \le h$ is never inside the invariant interval at any stage of the computation.
Therefore, if $K$ is stored in any position $1 \le j \le \lfloor N/2 \rfloor$, Algorithm U can never reach a state where it compares $K$ with $T[j]$, and it must terminate unsuccessfully.
Thus the algorithm is not correct under this initialization.
(b) $i \leftarrow \lfloor N/2 \rfloor,\quad m \leftarrow \lfloor N/2 \rfloor$ (alternative rounding)
Changing the rounding does not change the structure of the initial interval. Let $h = \lfloor N/2 \rfloor$. In all cases:
$$ i = h,\quad m = h \quad \Longrightarrow \quad (i, i+m] = (h, 2h] $$
The same containment holds:
$$ (1,h] \cap (i,i+m] = \varnothing. $$
Thus the same failure mechanism applies:
- any key in the lower half of the table is excluded from the invariant interval,
- the updates of U3 and U4 preserve the exclusion,
- such keys are never tested.
Therefore the modification in (b) also destroys correctness.
Conclusion
Algorithm U is correct because U1 initializes an interval $(i,i+m]$ that covers the entire index set $1 \le j \le N$, and U3–U4 preserve the invariant that the true position remains inside this interval whenever it exists.
Both proposed modifications replace this full-covering initial interval with a strictly smaller one that excludes at least one entire region of indices, and the algorithm never expands the interval afterward. Consequently, keys located outside the initial interval can never be found.
Hence neither modification preserves correctness of Algorithm U. ∎