A097384 - OEIS

%I #6 Nov 26 2017 21:49:57

%S 0,2,3,6,9,11,13,17,21,25,29,32,35,38,41,46,51,56,61,66,71,76,81,85,

%T 89,93,97,101,105,109,113,119,125,131,137,143,149,155,161,167,173,179,

%U 185,191,197,203,209,214,219,224,229,234,239,244,249,254,259,264,269,274

%N 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.

%C Pure binary search with equality.

%D 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

%F n + a_{floor((n-1)/2)} + a_{ceiling((n-1)/2)}.

%e a_5 = 9 = 5 + a_2 + a_2; this is the smallest example where choosing the middle value is not optimal.

%Y See A097383 for the sequence with an optimized binary search. A003314 is the sequence with only 2-way comparisons.

%K easy,nonn

%O 1,2

%A _Franklin T. Adams-Watters_, Aug 11 2004