TAOCP 6.2.1 Exercise 29

Let $A_i = K_i$.

taocpmathematicsalgorithmsvolume-3medium

Section 6.2.1: Searching an Ordered Table

Exercise 29. [22] [22] (Paul Feldman, 1985.) Instead of assuming that K, < Kz <--: < Kn, assume only that Ky(1) < Kyi) < +--+ < Kycny where the permutation p(1)p(2)...p(N) is an involution, and p(j) = j for all even values of 7. Show that we can locate any given key K, or determine that K is not present, by making at most 2|lg N| +1 comparisons.

Verified: no
Solve time: 2m49s

Let $A_i = K_i$. The given condition is that there exists a permutation $p$ such that

$$ K_{p(1)} < K_{p(2)} < \cdots < K_{p(N)}, $$

and $p$ is an involution with $p(j)=j$ for every even $j$.

Define a virtual array

$$ B[j] := A_{p(j)} = K_{p(j)} \qquad (1 \le j \le N). $$

By the hypothesis, this array satisfies

$$ B[1] < B[2] < \cdots < B[N], $$

so $B$ is strictly increasing in the index order $1,\dots,N$. This is a totally ordered sequence, and we can perform binary search on it.

The key point is that for any index $j$, we can access $B[j]$ by computing $p(j)$ and reading $A_{p(j)}$. Each such access requires exactly one comparison between the query key $K$ and a table entry.

Search procedure

We perform standard binary search on the index interval $[1,N]$ in the virtual array $B$.

Maintain integers $a \le b$, initially $a=1$, $b=N$.

While $a \le b$, let

$$ m = \left\lfloor \frac{a+b}{2} \right\rfloor. $$

Compare $K$ with $B[m] = A_{p(m)}$.

  • If $K = B[m]$, terminate successfully.
  • If $K < B[m]$, set $b = m-1$.
  • If $K > B[m]$, set $a = m+1$.

Correctness

The correctness is immediate from the fact that $B[1] < \cdots < B[N]$. Since $B$ is strictly increasing, standard binary search invariants apply:

At every step, if $K$ is present in the structure, it must lie in the current interval $[a,b]$, because all elements outside the interval are strictly smaller (to the left) or strictly larger (to the right) than the midpoint value $B[m]$, depending on the comparison outcome.

Thus the search maintains correctness exactly as in binary search on a sorted array.

The involution property of $p$, including the constraint $p(j)=j$ for even $j$, plays no role in correctness beyond guaranteeing that $p$ is a permutation and hence that $B$ is a rearrangement of the original keys.

Comparison bound

Each iteration performs exactly one comparison between $K$ and a table entry $A_{p(m)}$.

The interval size halves at each step, so the number of iterations is at most

$$ \lceil \lg N \rceil + 1. $$

Hence the total number of comparisons is at most

$$ \lceil \lg N \rceil + 1 \le 2\lceil \lg N \rceil + 1. $$

Conclusion

We can locate $K$ or determine that it is absent using standard binary search on the reordered sequence $B[j]=K_{p(j)}$, requiring at most $\lceil \lg N \rceil + 1$ comparisons, which is within the required bound $2|\lg N|+1$.