Why is the average of comparisons of k-ary search is k* ln(N) / ln(k)?

Question

I know that the function is executed ln(N)/ln(K) times;but in average does it make K operations?

Questions:

1. is there any proof that k*ln(N)/ln(K) is the average number of executions?
2. If this formula is correct, then ternary search will be the fastest search as k/ln(k) will be minimum (for integers) because 3 is the closest integer to "e" (the real minimum) which is very easy to prove using differentiation.

Furthermore I believe that ternary search is faster;because I made a comparing computer program.

Answer 1

1. No, because the correct answer is (k - 1) log n / log k + O(1): only k - 1 comparisons (really only lg k + O(1)) are needed to reduce the size of the search range by a factor of k. This can be proved by induction on the recurrence T(1) = 1, T(2) = 2, T(n) = (k - 1) + T(n / k).

2. The integer argmin of (k - 1) / log k occurs at 2. There are plenty of computer architectural reasons why ternary search might be faster anyway.