TAOCP 6.2.1 Exercise 23

Let the given search algorithm be represented by a finite decision tree $T$.

taocpmathematicsalgorithmsvolume-3medium

Section 6.2.1: Searching an Ordered Table

Exercise 23. [25] [25] The binary search algorithm of H. Bottenbruch, mentioned at the close of this section, avoids testing for equality until the very end of the search. (During the algorithm we know that Ki < K < Ku+i, and the case of equality is not examined until 1 = u.) Such a trick would make Program B run a little bit faster for large N, since the ‘JE’ instruction could be removed from the inner loop. (However, the idea wouldn’t really be practical since lg N is always rather small; we would need N > 2° in order to compensate for the extra work necessary on a successful search, because the running time (18lg N, 16)u of (5) is “decreased” to (17.5lg N + 17)u!)

Show that every search algorithm corresponding to a binary tree can be adapted to a search algorithm that uses two-way branching (< versus > ) at the internal nodes of the tree, in place of the three-way branching (< , =, or > ) used in the text’s discussion. In particular, show how to modify Algorithm C in this way.

Verified: no
Solve time: 5m08s

Let the given search algorithm be represented by a finite decision tree $T$. Each internal node is labeled by an index $j$ and performs a comparison between the search key $K$ and $K_j$, with three outgoing edges labeled

$$ K < K_j,\quad K = K_j,\quad K > K_j. $$

Each leaf corresponds either to successful termination at some key $K_i$ or to unsuccessful termination.

We construct a new algorithm corresponding to a binary decision tree $T'$ that uses only comparisons of the form $K < K_j$ at internal nodes, with all equality testing postponed to the end.

1. Construction of the two-way branching tree

We transform $T$ recursively.

At every internal node labeled $j$, replace the ternary test by the binary test

$$ \text{if } K < K_j \text{ then go to the left subtree;} \quad \text{else go to the right subtree.} $$

The right subtree of $T'$ is defined as the union of the original $=$ and $>$ subtrees of $T$.

Thus every node in $T'$ corresponds to the same comparison as in $T$, but collapses the outcomes $K = K_j$ and $K > K_j$ into a single branch.

Leaves are unchanged: each successful leaf still corresponds to some key $K_i$, and unsuccessful leaves remain unsuccessful.

No equality test is performed during traversal.

2. Key structural observation

Fix any key $K$. Consider its execution path in $T$.

At each internal node comparing with $K_j$, exactly one of the following holds:

  • If $K < K_j$, the path goes to the left subtree in both $T$ and $T'$.
  • If $K > K_j$, the path goes to the right subtree in $T$, and also to the right subtree in $T'$.
  • If $K = K_j$, the original algorithm terminates immediately at that node.

Crucially, the equality case does not influence any further branching structure below that node in $T$, since it is already a terminal configuration.

Therefore, removing equality edges does not alter the set of comparisons that determine which leaf is consistent with the strict inequalities satisfied by $K$.

3. Correctness of the transformed tree

We prove that $T'$ returns the correct search result.

Lemma 1 (Consistency of paths)

For every key $K$, the path taken in $T'$ is exactly the path in $T$ with all equality-termination steps removed, but with all strict comparisons preserved.

Proof. At each node, both algorithms branch identically on $K < K_j$ versus $K \ge K_j$. If $K > K_j$, both go right; if $K < K_j$, both go left. The only difference is that $T$ may terminate early when $K = K_j$, while $T'$ continues. ∎

Lemma 2 (Leaf identification is preserved)

Each key $K_i$ corresponds to a unique leaf determined solely by strict inequalities with other keys.

Proof. In a correct search tree over ordered keys, reaching the successful leaf for $K_i$ is determined by the pattern of comparisons

$$ K_i < K_j \quad \text{or} \quad K_i > K_j \quad (j \ne i), $$

while equality is used only to terminate early when the search key equals the stored key. These strict relations uniquely determine the region of the tree leading to $K_i$. Removing equality tests does not change any of these strict comparisons, hence does not change the leaf reached. ∎

Lemma 3 (No incorrect merging of distinct keys)

If $K \ne K_i$, then $K$ cannot reach the successful leaf for $K_i$ in $T'$.

Proof. Since $T$ is correct, the leaf for $K_i$ is characterized by a consistent set of strict inequalities separating $K_i$ from all other keys. Any $K \ne K_i$ violates at least one of these inequalities and is routed differently at the first distinguishing node. Since $T'$ preserves all strict inequality decisions, it cannot incorrectly reach that leaf. ∎

4. Final equality test

Because equality is not used during traversal, the algorithm must verify success at termination.

Thus, when $T'$ reaches a leaf corresponding to some key $K_i$, it performs a single final test:

$$ \text{if } K = K_i \text{ then report success; else report failure.} $$

This final check distinguishes successful from unsuccessful searches without affecting the traversal structure.

Algorithm C in the text is a three-way branching binary search that performs an equality test at every iteration.

Let the array be $K_1 < K_2 < \cdots < K_N$. Algorithm C repeatedly computes a middle index $j$ and performs:

$$ \text{if } K < K_j \text{ then search left;} \quad \text{if } K = K_j \text{ then stop;} \quad \text{if } K > K_j \text{ then search right.} $$

To obtain the required two-way version, replace each iteration by:

$$ \text{if } K < K_j \text{ then set } U \leftarrow j-1; \quad \text{else set } L \leftarrow j+1. $$

No equality test is performed inside the loop.

The loop terminates when $L > U$, at which point a single candidate index $j$ (if any) is checked once:

$$ \text{if } K = K_j \text{ then success; else failure.} $$

This removes the internal equality branch exactly as required, and it corresponds to collapsing the ternary decision at each node into a binary decision $<$ versus $\ge$.

6. Conclusion

Every search algorithm represented by a ternary decision tree can be converted into an equivalent two-way branching algorithm by replacing each comparison node

$$ (K < K_j,; K = K_j,; K > K_j) $$

with a binary decision

$$ K < K_j \quad \text{versus} \quad K \ge K_j, $$

and deferring all equality tests to a single verification at termination.

Applied to Algorithm C, this eliminates all equality checks in the inner loop while preserving correctness and the structure of the search.