At 07:20 -0500 on 10/28/2013, John Gilmore wrote about Re: Linear
search vs binary:
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
An example of this method in use are VSAM Indexes. This shortend key
is the way the keys in the VSAM index are stored. As soon as you find
a higher key, you know the record you are looking for or wanting to
insert goes into that CI.
