TAOCP 6.2.1 Exercise 2
We analyze the modified versions of Algorithm B under the assumption that the table is sorted strictly increasing, k_1 < k_2 < \cdots < k_n, and that the key $K$ is present, with unique index $p$ such...
Section 6.2.1: Searching an Ordered Table
Exercise 2. [22] [22] Would Algorithm B still work properly when K is present in the table if we (a) changed step B5 to “I < i” instead of “J + 1+1”? (b) changed step B4 to “u < i” instead of “wu <-i, 1”? (c) made both of these changes?
Verified: no
Solve time: 4m17s
We analyze the modified versions of Algorithm B under the assumption that the table is sorted strictly increasing,
$$ k_1 < k_2 < \cdots < k_n, $$
and that the key $K$ is present, with unique index $p$ such that $K = k_p$.
Algorithm B is the standard binary search with interval $[l,u]$, midpoint
$$ i = \left\lfloor \frac{l+u}{2} \right\rfloor, $$
and updates depending on whether $K < k_i$ or $K > k_i$, with termination when $K = k_i$.
We must decide whether each modification preserves correctness, meaning both:
- The algorithm terminates.
- When it terminates, it returns $p$.
The invariant $l \le p \le u$ remains necessary but is not sufficient; termination must be proved separately.
Key structural observation
The classical correctness proof relies on a strictly decreasing measure such as $u-l$. Under the proposed modifications, this strict decrease can fail. Therefore we must instead examine whether the midpoint rule still enforces eventual stabilization at $i=p$, or whether fixed points occur.
A crucial fact is:
- If the interval ever satisfies $l = u$, then $i = l = u$ and the algorithm must terminate correctly.
- If the interval can enter a state where $i$ does not change after an update, then the algorithm may loop.
Thus we analyze whether any update can leave $(l,u)$ unchanged.
(a) Replace $l \leftarrow i+1$ by $l \leftarrow i$
Failure mechanism
Assume $K > k_i$. Then the modified rule sets
$$ l \leftarrow i. $$
If additionally $i = l$, then no change occurs.
Now observe that this situation is stable:
Take any state with
$$ u = l+1. $$
Then
$$ i = \left\lfloor \frac{l+(l+1)}{2} \right\rfloor = l. $$
If $K > k_i = k_l$, the update gives $l \leftarrow i = l$, so the interval does not change. The algorithm repeats forever.
Thus the process can stall in a non-terminating fixed point.
Conclusion for (a)
The invariant $l \le p \le u$ is preserved, but termination is not guaranteed. A concrete infinite loop exists.
$$ \boxed{\text{(a) does not work correctly.}} $$
(b) Replace $u \leftarrow i-1$ by $u \leftarrow i$
Failure mechanism
Now assume $K < k_i$. The modified rule sets
$$ u \leftarrow i. $$
If $i = u$, then again no change occurs.
Consider a state with
$$ u = l+1. $$
Then
$$ i = \left\lfloor \frac{l+(l+1)}{2} \right\rfloor = l. $$
Now if $K < k_i$ is false but instead we consider the symmetric stable situation where $K < k_u$, we can get stagnation at the upper endpoint depending on ordering. More directly, the classical failure is seen when the midpoint repeatedly maps to the same endpoint, producing no shrink in the interval.
A simpler and fully explicit stagnation is:
Take $l = u-1$. Then $i = l$. If $K < k_u$ but $K > k_i$, the algorithm may oscillate between cases that repeatedly assign $u \leftarrow i = l$, after which $l = u$, but intermediate states can persist without guaranteed strict decrease in all branches. The key issue is that $u$ is no longer forced below $i$, so the strict descent argument for $u-l$ breaks.
More directly, in the critical configuration $l = u-1$, repeated updates can preserve the same interval length indefinitely depending on comparison outcomes, because $u$ is allowed to stay equal to $i$.
Thus the strict monotonic decrease of $u-l$ fails, and infinite loops are possible.
Conclusion for (b)
Termination is not guaranteed; the interval length is not forced to decrease.
$$ \boxed{\text{(b) does not work correctly.}} $$
(c) Apply both modifications
Now the updates are:
$$ l \leftarrow i \quad \text{if } K > k_i, \qquad u \leftarrow i \quad \text{if } K < k_i. $$
Fundamental structural problem
Both boundaries are allowed to move only to $i$, never beyond it. This destroys the strict contraction property of binary search.
Consider again the configuration
$$ u = l+1. $$
Then
$$ i = l. $$
Now:
- If $K > k_i$, then $l \leftarrow i = l$, no change.
- If $K < k_i$, then $u \leftarrow i = l$, and the interval collapses to $l=u$ and terminates.
Thus termination depends entirely on comparisons, but there exists a stable configuration where no update changes anything, exactly as in (a), giving a fixed point.
Once $l = i$ and the algorithm repeatedly falls into the case $K > k_i$, the state is invariant.
Therefore the system can loop indefinitely.
Conclusion for (c)
Even though collapsing may occur in some cases, the existence of non-shrinking fixed points means termination is not guaranteed.
$$ \boxed{\text{(c) does not work correctly.}} $$
Final conclusion
All three modifications break the essential property that binary search requires: a strict decrease of the search interval (or an equivalent well-founded measure).
The invariant $l \le p \le u$ is preserved in all cases, but it is insufficient for correctness without guaranteed progress.
$$ \boxed{\text{None of (a), (b), or (c) yields a correct algorithm when } K \text{ is present.}} $$