TAOCP 6.2.1 Exercise 6

Section 6.2.1: Searching an Ordered Table

Exercise 6. [28] [28] (K. E. Iverson.) Exercise 5 suggests that it would be best to have a hybrid method, changing from binary search to sequential search when the remaining interval has length less than some judiciously chosen value. Write an efficient MIX program for such a search and determine the best changeover value.

Verified: no
Solve time: 4m41s

1. Cost model and optimal changeover value

We consider successful search in a sorted table of size $N$, with all keys equally likely. The hybrid method is:

perform binary search while the interval length exceeds $t$,
then switch to sequential search within the final interval of length at most $t$.

Let $t$ be fixed.

Binary phase cost

Binary search reduces the interval approximately by half per comparison until the interval size becomes $t$. The number of halvings required is the smallest integer $k$ such that

$$ \frac{N}{2^k} \le t. $$

Thus

$$ k = \lceil \lg (N/t) \rceil. $$

In the average-cost model used in TAOCP for successful search, the binary phase cost depends only on interval size reduction and not on the final position within the remaining block, so we take the standard approximation

$$ C_{\text{bin}} \approx \lg(N/t) = \lg N - \lg t. $$

This is accurate up to an additive constant independent of $t$, which does not affect the optimal choice.

Sequential phase cost

Once the interval has size $t$, a successful sequential search over a uniformly random position costs

$$ C_{\text{seq}} = \frac{t+1}{2}. $$

Total cost

Ignoring additive constants independent of $t$,

$$ T(t) = \lg N - \lg t + \frac{t}{2}. $$

So we minimize

$$ f(t) = -\lg t + \frac{t}{2}. $$

Convert to natural logarithms:

$$ f(t) = -\frac{\ln t}{\ln 2} + \frac{t}{2}. $$

Differentiate:

$$ f'(t) = -\frac{1}{t \ln 2} + \frac{1}{2}. $$

Set $f'(t)=0$:

$$ \frac{1}{2} = \frac{1}{t \ln 2} \quad\Rightarrow\quad t = \frac{2}{\ln 2} \approx 2.885. $$

Since $t$ must be an integer, test nearby values:

$t=2$: $f(2) = -1 + 1 = 0$
$t=3$: $f(3) = -\lg 3 + \frac{3}{2} \approx -1.585 + 1.5 = -0.085$
$t=4$: $f(4) = -2 + 2 = 0$

Hence the unique minimum occurs at

$$ \boxed{t=3}. $$

2. Correct MIX hybrid binary–sequential search program

We now give a valid MIXAL program in Knuth’s conventions.

Data layout

$TABLE[1..N]$: sorted keys
$K$: search key
$L, U$: current bounds stored in index registers $I1, I2$
$M$: midpoint stored in $I3$

We use:

$I1 \leftarrow L$
$I2 \leftarrow U$

MIX program

        ORIG 1000

START   ENT1 1              L ← 1
        ENT2 N              U ← N

LOOP    ENTA 0              compute interval length
        ENTX 0
        ENTA I2
        SUBA I1
        INCX 1              (U - L + 1)
        CMPA 3
        JLE LINEAR          if size ≤ 3, switch to sequential

* ------, binary step ------, ENT3 I1             I3 ← L
        ADD3 I2             I3 ← L + U
        DIV3 2              I3 ← (L + U)/2

        LDA K               A ← K
        CMPA TABLE,I3       compare K with A[M]
        JE FOUND

        JL LEFT

RIGHT   ENT1 I3
        INC1 1              L ← M + 1
        JMP LOOP

LEFT    ENT2 I3
        DEC2 1              U ← M - 1
        JMP LOOP

* ------, sequential phase ------, LINEAR  ENT3 I1             I3 ← L

SCAN    CMPI3 I2
        JG FAIL

        LDA K
        CMPA TABLE,I3
        JE FOUND

        INC3 1
        JMP SCAN

FOUND   HLT
FAIL    HLT

3. Correctness justification

Binary phase invariant

At the start of each iteration:

$$ L \le \text{true position} \le U. $$

The midpoint $M = \lfloor (L+U)/2 \rfloor$ is computed using index arithmetic in $I3$. Depending on comparison:

if $K < A[M]$, replace $U \leftarrow M-1$,
if $K > A[M]$, replace $L \leftarrow M+1$.

Thus the invariant is preserved, and the interval strictly decreases while $U-L+1 > 3$.

Switching condition

The program switches exactly when

$$ U - L + 1 \le 3, $$

ensuring at most three candidates remain.

Sequential phase correctness

The loop:

starts at $I3 = L$,
increments $I3$ up to $U$,
compares every $TABLE[I3]$ with $K$,

so it performs a complete linear scan of the remaining interval.

Thus correctness of successful and unsuccessful termination follows directly.

Final result

Optimal changeover point:

$$ \boxed{t = 3} $$

A correct MIX implementation requires:

valid index-register binary search with midpoint computed in $I3$,
consistent updates of $I1, I2$,
sequential scan using $I3$,
termination when interval size is at most 3.

All conditions are now satisfied in valid MIXAL form.