TAOCP 6.2.1 Exercise 14

Let $N>1$ be arbitrary.

taocpmathematicsalgorithmsvolume-3medium

Section 6.2.1: Searching an Ordered Table

Exercise 14. [21] [21] Explain how to extend Algorithm F so that it will apply for all N > 1.

Verified: yes
Solve time: 1m23s

Solution

Let $N>1$ be arbitrary. Choose $k$ such that

$F_{k+1} \ge N+1 \quad \text{and} \quad F_k < N+1.$

Define

$M = F_{k+1}-1,$

so that $M \ge N$ and $M+1 = F_{k+1}$ is a Fibonacci number.

Extend the table by introducing fictitious records $R_{N+1},\dots,R_M$ whose keys satisfy

$K_{N+1} = K_{N+2} = \cdots = K_M = +\infty,$

where $+\infty$ denotes a value greater than every key in the original table. The original ordered property is preserved for the extended sequence

$K_1 < K_2 < \cdots < K_N < K_{N+1} = \cdots = K_M.$

Algorithm F is now applied to the extended table of size $M$ with the same search argument $K$, and with initialization based on $M+1 = F_{k+1}$:

$i \leftarrow F_k,\quad p \leftarrow F_{k-1},\quad q \leftarrow F_{k-2}.$

All subsequent steps of Algorithm F are executed without change.

Correctness follows from preservation of the comparison structure. For $1 \le j \le N$, comparisons $K \lessgtr K_j$ are identical to those in the original problem. For $N<j\le M$, the comparison $K < K_j$ holds for every finite $K$, hence step F2 always directs execution to F3 when $i$ lies in the fictitious region. The update rules in F3 and F4 maintain the invariant that $(p,q)$ remain consecutive Fibonacci numbers and that $i$ remains consistent with a Fibonacci partition of the current interval in the extended index set ${1,\dots,M}$.

If the search reaches an index $j>N$, then every further comparison is with a key $+\infty$, so the algorithm repeatedly follows the left-branch update until the condition $q=0$ or $p=1$ is met, at which point the algorithm terminates unsuccessfully. No successful termination can occur at a fictitious index since $K \ne +\infty$.

If the key $K$ equals some $K_j$ with $1 \le j \le N$, then $j$ is also an index in the extended table, and the execution path in Algorithm F on the extended structure coincides with the path that would occur if $N+1$ were exactly a Fibonacci number. Hence the algorithm reaches $i=j$ before any fictitious comparison forces termination.

Thus Algorithm F applied to the padded table of size $M$ correctly performs search for all $N>1$ without requiring $N+1$ to be a Fibonacci number. This completes the proof. ∎