TAOCP 6.2.1 Exercise 1

Section 6.2.1: Searching an Ordered Table

Exercise 1. [21] [21] Prove that if u < / in step B2 of the binary search, we have u = /, 1 and Ku < K < k;. (Assume by convention that Ko =, oo and Ky+1 = +00, although these artificial keys are never really used by the algorithm so they need not be present in the actual table.)

Verified: yes
Solve time: 2m30s

---

Let $l$ and $u$ be the current indices in Algorithm B (binary search on a sorted table $K_1 < \cdots < K_n$), with sentinels $K_0 = -\infty$ and $K_{n+1} = +\infty$.

We use the standard binary search invariant:

$$ (*) \quad \forall i < l,; K_i < K \qquad\text{and}\qquad \forall i > u,; K_i > K. $$

We also establish the auxiliary invariant:

$$ (\dagger)\quad l \le u + 1 \text{ at all times.} $$

1. Proof of $K_u < K < K_l$ when $u < l$

Assume $u < l$.

Since $u < l$, we have $u < l$, hence $u$ satisfies the condition $i < l$. Applying $(*)$ gives

$$ K_u < K. $$

Similarly, since $l > u$, the index $l$ satisfies $i > u$. Applying $(*)$ gives

$$ K_l > K. $$

Thus,

$$ K_u < K < K_l. $$

2. Proof that $u = l - 1$ when $u < l$

We first prove the invariant $(\dagger)$: $l \le u+1$ is preserved by every iteration.

Let $j = \left\lfloor \frac{l+u}{2} \right\rfloor$. Then always

$$ l \le j \le u. $$

Case 1: $K < K_j$.

The algorithm sets $u' = j$, $l' = l$. Then

$$ l' = l \le j+1 = u' + 1. $$

Case 2: $K > K_j$.

The algorithm sets $l' = j$, $u' = u$. Since $j \le u$,

$$ l' = j \le u \le u+1 = u' + 1. $$

Thus $l \le u+1$ is preserved in both cases, so $(\dagger)$ holds throughout execution.

Now assume $u < l$ at some step. Combining this with $(\dagger)$, we obtain

$$ u < l \le u+1. $$

The only integer satisfying this chain of inequalities is $l = u+1$. Therefore,

$$ u = l - 1. $$

Conclusion

When $u < l$ in step B2 of binary search, the maintained invariants imply

$$ u = l - 1 \quad\text{and}\quad K_u < K < K_l. $$

This completes the proof. ∎