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.

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

Offset

1,2

Comments

Pure binary search with equality.

References

Hsien-Kuei Hwang, S Janson, TH Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint, 2016; http://140.109.74.92/hk/wp-content/files/2016/12/aat-hhrr-1.pdf. Also Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585

Links

Table of n, a(n) for n=1..60.

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: A127590 A118730 A291669 * A067886 A227000 A338546

Adjacent sequences: A097381 A097382 A097383 * A097385 A097386 A097387

Keyword

easy,nonn

Author

Franklin T. Adams-Watters, Aug 11 2004

Status

approved