id:A097384 - OEIS Search Results

Search: id:A097384

Displaying 1-1 of 1 results found.

page 1

Total number of comparisons to find each of the values 1 through n using a binary search with 3-way comparisons (less than, equal and greater than), always choosing the mid-most value to compare to.

+0
2

0, 2, 3, 6, 9, 11, 13, 17, 21, 25, 29, 32, 35, 38, 41, 46, 51, 56, 61, 66, 71, 76, 81, 85, 89, 93, 97, 101, 105, 109, 113, 119, 125, 131, 137, 143, 149, 155, 161, 167, 173, 179, 185, 191, 197, 203, 209, 214, 219, 224, 229, 234, 239, 244, 249, 254, 259, 264, 269, 274 (list; graph; listen)

	OFFSET	`1,2`
	COMMENT	`Pure binary search with equality.`
	FORMULA	`n + a_{floor((n-1)/2)} + a_{ceiling((n-1)/2)}.`
	EXAMPLE	`a_5 = 9 = 5 + a_2 + a_2; this is the smallest example where choosing the middle value is not optimal.`
	CROSSREFS	`See A097383 for the sequence with an optimized binary search. A003314 is the sequence with only 2-way comparisons.` `Sequence in context: A058958 A127590 A118730 this_sequence A067886 A057127 A007780` `Adjacent sequences: A097381 A097382 A097383 this_sequence A097385 A097386 A097387`
	KEYWORD	`easy,nonn`
	AUTHOR	`Frank Adams-Watters (FrankTAW(AT)Netscape.net), Aug 11 2004`

page 1

Search completed in 0.003 seconds

Last modified November 27 22:38 EST 2009. Contains 167602 sequences.

AT&T Labs Research