|
| |
|
|
A097384
|
|
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.
|
|
1
| |
|
|
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; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,2
|
|
|
COMMENTS
| 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: A189708 A127590 A118730 * A067886 A176189 A057127
Adjacent sequences: A097381 A097382 A097383 * A097385 A097386 A097387
|
|
|
KEYWORD
| easy,nonn
|
|
|
AUTHOR
| Frank Adams-Watters (FrankTAW(AT)Netscape.net), Aug 11 2004
|
| |
|
|
