Re: Binary search (was numbering schemes)

[Fred M Jacobson <fred -at- BOOLE -dot- COM>]

> What a wonderful statistic. Does it depend on the size of the
> dictionary? (And how do you account for the OED, where you
> might have to "flip" between volumes?)

Vicki-

Way back in 1968, when I was a T.A. for Arthur Kahn in a "Computers &
Society" course, he used this search method as a "parlor trick" in a
large lecture.  He brought a telephone book and stated, "I can find any
name you choose out of the residence listing by asking just 20 yes-or-
no questions."  He had a student pick a name.  Then he opened the phone
book to the middle of the residence listing and asked, "Is the name before
Jensen."  Based on the answer he eliminated half of the book and repeated
the process.  Using 20 questions he could find an item in a sorted list of
2**20 (2 raised to the 20th power) items.  That's 1,048,576, more than
enough for most residential listings, even allowing for a little sloppiness
in selecting the midpoint of the sublist of remaining names.

In general, ln2(n) (log base 2 of n) probes will find an item in a sorted
list of n items.  It takes 9 probes to find a page in a book of 500 pages.
It takes more probes to find an entry in the OED than it does to find one
in the COD (Concise Oxford Dictionary).  Of course, people don't usually
search ordered lists this way.  Computer often do.

-Fred
--
INTERNET: fred -at- boole -dot- com          PHONE: (408) 526-3292  FAX: (408) 526-3055
USPS: Fred Jacobson / Boole & Babbage / 3131 Zanker Road / San Jose CA 95134