There is one respect in which this thread on binary search has been
unsatisfactory. It has concerned itself only with match-seeking
binary search, and bounds-seeking binary search is at least as
useful.
A greatest lower bound (GLB) on a search argument or a least upper
bound (LUB) on it came be searched for in the same tables in which
matches are sought.
An example will help here. Suppose that we have a set of keywords
{start, stop, tergiversate, waffle, dally, wait, dither}
If we put them into lexicographic sequence padded on the right with
nuls, x'00', we get
dallyµµµµµµµ, 2
ditherµµµµµµ, 2
startµµµµµµµ, 2
stopµµµµµµµ, 3
tergiversate, 1
waffleµµµµµµ, 3
waitµµµµµµµ,3
in which 'µ' is a nonce representation of a nul character and the
integer following it is the leftmost character position at which an
element differs from its predcecessor and/or successor. (The first
element has no predecessor; the last one has no successor.)
This information can be used to recognize any case-independent
disambiguating truncation of a keyword as an instance of it. For
example,
o sta, star, start can be recognized as instances
of start,
o sto, stop can be recognized as instances of
stop, and
o the recognition of either s or st, which are not
disambiguating truncations, can be avoided.
What is needed is a 1) a LUB-seeking binary search of the table, a
test to ensure that the search argument S and table element T(lubsub)
'S' = 'T(lubsub)'(1,k'S), and a test to ensure that k'S is not smaller
than the minimal disambiguating character count for T(lubsub).
In general bound-seeking binary search can be used to evaluate any
step function. There are many more uses for it than there are for
match-seeking binary search.
Quantity discounts, empirical frequency distributions having unequal
class intervals, Knuth's q, etc., etc., can all be dealt with in this
way. Monte Carlo calculations and much gaming, which are comprised
chiefly of sampling from EFDs, go very much faster.
John Gilmore, Ashland, MA 01721 - USA
