Knuth's analysis of match-seeking binary search deals in an ordered
set of n keys
{k(1) < k(2) < . . . < k(i) < . . . k(n)}
and another set of 2n + 1 searches, viz.,
o one such that s < k(1), which fails,
o n - 1 such that k(i) < s < k(i+1),
i = 1, 2, . . . , n - 1, all of which fail,
o n such that s = k(j), j = 1, 2, . . ., n, all
of which succeed, and
o one such that s > k(n), which fails.
He shows that the total number of ternary comparisons required for
these 2n + 1 searches when his Algorithm B is used
M(n) = 2[(n + 1)q + 2e] – n,
with q = floor[log2(n + 1)] and e = n - (2^q - 1) ; and he shows that
this number is a minimum.
Knuth has also provided a recursive (dynamic programming) scheme for
constructing not tables but optimal explicit binary-search trees when
the frequencies of these 2n + 1 sets of search arguments are not
equal.
These classical results are in presented in volume 2 of TACP. They
are not really open to exception.
Departures from Knuth's assumptions are another matter. In very
different circumstances other schemes may be optimal. Even for them
some qualitative results have been established firmly. One of the
most important of these results is that match frequencies, counts of
the instances of s = k(i), alone are never adequate. Counts of the
frequencies of the n + 1 kinds of failures enumerated above are needed
too. Analyses based upon match frequencies alone have a long history
of yielding bad, suboptimal methods.
John Gilmore, Ashland, MA 01721 - USA
