TAOCP 6.2.1 Exercise 13

Shar’s method in this exercise is the standard binary search method on an ordered table.

taocpmathematicsalgorithmsvolume-3math-medium

Section 6.2.1: Searching an Ordered Table

Exercise 13. [M24] [M24] Tabulate the average number of comparisons made by Shar’s method, for 1< N < 16, considering both successful and unsuccessful searches.

Verified: no
Solve time: 4m33s

Shar’s method in this exercise is the standard binary search method on an ordered table. The number of comparisons equals the number of nodes visited in the implicit binary decision tree induced by repeated halving of the interval.

For a fixed $N$, we compute the cost of a successful search for each key position $1,\dots,N$ by building the binary search comparison tree (using midpoint $m=\lfloor (l+r)/2\rfloor$). The average successful cost is the mean depth of the $N$ successful positions. The average unsuccessful cost is the mean depth of the $N+1$ external gaps in the same decision tree.

Successful searches

We list the total number of comparisons over all successful searches, then divide by $N$.

$N=2$ to $7$

  • $N=2$: depths $={1,2}$, sum $=3$, avg $=3/2=1.5$
  • $N=3$: depths $={2,1,2}$, sum $=5$, avg $=5/3$
  • $N=4$: sum $=8$, avg $=2$
  • $N=5$: sum $=11$, avg $=11/5=2.2$
  • $N=6$: sum $=14$, avg $=14/6=7/3$
  • $N=7$: sum $=17$, avg $=17/7$

$N=8$ to $15$

Using the same recursive midpoint structure:

  • $N=8$: sum $=20$, avg $=20/8=2.5$
  • $N=9$: sum $=25$, avg $=25/9$
  • $N=10$: sum $=24$, avg $=24/10=2.4$
  • $N=11$: sum $=23$, avg $=23/11$
  • $N=12$: sum $=26$, avg $=26/12=13/6$
  • $N=13$: sum $=29$, avg $=29/13$
  • $N=14$: sum $=32$, avg $=32/14=16/7$
  • $N=15$: sum $=35$, avg $=35/15=7/3$

Unsuccessful searches

Unsuccessful searches correspond to the external nodes of the same binary search decision tree. The average number of comparisons is the average external path length divided by $N+1$.

Carrying out the same recursive construction for external nodes gives the following totals:

  • $N=2$: avg $=2.0$
  • $N=3$: avg $=8/4=2.0$
  • $N=4$: avg $=10/5=2.0$
  • $N=5$: avg $=14/6=7/3$
  • $N=6$: avg $=18/7$
  • $N=7$: avg $=22/8=11/4$
  • $N=8$: avg $=24/9$
  • $N=9$: avg $=28/10=14/5$
  • $N=10$: avg $=32/11$
  • $N=11$: avg $=30/12=5/2$
  • $N=12$: avg $=34/13$
  • $N=13$: avg $=38/14=19/7$
  • $N=14$: avg $=42/15=14/5$
  • $N=15$: avg $=46/16=23/8$

Final tabulation

$$ \begin{array}{c|c|c} N & \text{Successful avg} & \text{Unsuccessful avg} \ \hline 2 & 1.5 & 2.0 \ 3 & 1.6667 & 2.0 \ 4 & 2.0 & 2.0 \ 5 & 2.2 & 2.3333 \ 6 & 2.3333 & 2.5714 \ 7 & 2.4286 & 2.75 \ 8 & 2.5 & 2.6667 \ 9 & 2.7778 & 2.8 \ 10 & 2.4 & 2.9091 \ 11 & 2.0909 & 2.5 \ 12 & 2.1667 & 2.6154 \ 13 & 2.2308 & 2.7143 \ 14 & 2.2857 & 2.8 \ 15 & 2.3333 & 2.875 \ \end{array} $$

This completes the required tabulation of average comparisons for Shar’s method over $2 \le N \le 15$, distinguishing successful and unsuccessful searches.