Binary Search

[Franklin T. Adams-Watters]

I just got interested in the question of optimizing binary search.  The basic question is, given n values, what is the minimum number of comparisons needed to find each of the values 1 through n in a binary search tree?

(Note: we are assuming that the value searched for is one of the values in the tree; there are "misses".)

When we only allow two-way comparisons, the answer is A003314:
0,2,5,8,12,16,20,24,29,34,...

When we allow three-way comparisons (<, =, or >), things get more interesting.  In particular, the optimal search pattern does not always use the middle value for the first comparison; sometimes one of the adjacent values gives a better solution.

This happens first for n=5.  Checking first the middle value, 3, we will then require an additional comparison for any value other than 3, for a total of 4*2+1 = 9 comparisons.  However, checking 4 first, either 4 or 5 will be identified with a single comparison, while one additional comparison is all that is required to identify 1, 2, or 3.  The total is thus 3*2+2*1 = 8.

I have submitted two new sequences, A097383 and A097384, with respectively the number of comparisons required for an optimal comparison tree, and for a "pure" binary search.


-- 
Franklin T. Adams-Watters
16 W. Michigan Ave.
Palatine, IL 60067
847-776-7645


__________________________________________________________________
Switch to Netscape Internet Service.
As low as $9.95 a month -- Sign up today at http://isp.netscape.com/register

Netscape. Just the Net You Need.

New! Netscape Toolbar for Internet Explorer
Search from anywhere on the Web and block those annoying pop-ups.
Download now at http://channels.netscape.com/ns/search/install.jsp