Re: data structure for strings

On Sat, 12 Aug 2000, Brian Inglis wrote:

> >What about a binary search? You need 7.022 steps per search, which means
> >comparing a maximum of 14 (8 steps + 6 chars/word) bytes.
 

> I make it a minimum of 6 byte comparisons, a maximum of 41 byte
> comparisons (6 + 5 x 7), depending on the input word and its size
> and the distribution and sizes of the 130 words.

You're right. If the first n charactes match on word x, there is no guarantee that they also match on words (x +/- stepsize/2). Reminds me to not post late in the morning. :-)

   Simon

-- 
PGP public key available from http://phobos.fs.tum.de/pgp/Simon.Richter.asc
 Fingerprint: 10 62 F6 F5 C0 5D 9E D8  47 05 1B 8A 22 E5 4E C1
Hi! I'm a .signature virus! Copy me into your ~/.signature to help me spread!