TechWhirl (TECHWR-L) is a resource for technical writing and technical communications professionals of all experience levels and in all industries to share their experiences and acquire information.
For two decades, technical communicators have turned to TechWhirl to ask and answer questions about the always-changing world of technical communications, such as tools, skills, career paths, methodologies, and emerging industries. The TechWhirl Archives and magazine, created for, by and about technical writers, offer a wealth of knowledge to everyone with an interest in any aspect of technical communications.
Subject:Re: Binary search (was numbering schemes) From:Fred M Jacobson <fred -at- BOOLE -dot- COM> Date:Wed, 24 Nov 1993 15:20:30 PST
> 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?)
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.
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