Return to my Puzzle pages
Go to
my home page
© Copyright 2002, Jim Loy
On the Price Is Right, people are normally very pleased when confronted with the High Low Game. You are shown a valuable prize. And you must guess its price within a certain amount of time. You can guess as many times as you want, as long as the clock is still ticking. Bob Barker tells you if your guess should be "higher" or "lower." And the game is easy, as long as you retain some semblance of sanity. Here is an example. I will bid on a car (I don't know car prices):
10,000. Higher.
20,000. Lower.
15,000. Lower.
12,500. Higher.
14,000. Higher.
14,500. Lower.
14,250. Higher.
14,325. Lower.
14,300. Higher.
14,310. Higher.
14,320. Yes.
That wasn't too bad. That was relatively efficient, and it can be done very rapidly. Here is how a computer might do it, pretending that the price is less than or equal to 20,000:
10,000. Higher.
15,000. Lower.
12,500. Higher.
13,750. Higher.
14,375. Lower.
14,062. Higher.
14,218. Higher.
14,296. Higher.
14,335. Lower.
14,315. Higher.
14,325. Lower.
14,320. Right.
That actually took one more guess. But, in general, it is more efficient (takes fewer guesses). The computer did what is called a "binary search." And humans can approximate this technique, quite well, and even improve the search with knowledge of typical prices (maybe prices rounded to the nearest dollar end more often in 0 or 5?).
Such a search is not very common in puzzles. But it is very common in dictionary, phone book, or encyclopedia searches. In that case, you can speed up the search with your knowledge of the alphabet, and your knowledge of the distribution of more common letters.
And of course, computers do most of the searching nowadays. They use binary searches, and more complicated searches for a variety of reasons. For example, a binary search may not be the most efficient search on a hard disk, where many consecutive records are read into memory at once. Reading from a hard disk is slow; searching memory is fast. And the data is probably already organized into an easy to search form, such as a tree of some kind, which I will describe some other day.