Why is binary search faster than ternary search?

Question Detail: 

Searching an array of $N$ elements using binary search takes, in the worst case $\log_2 N$ iterations because, at each step we trim half of our search space. If, instead, we used 'ternary search', we'd cut away two-thirds of our search space at each iteration, so the worst case should take $\log_3 N < \log_2 N$ iterations...

It seems that ternary search is faster, so why do we use binary search?

Asked By : The Mean Square

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/29755

Answered By : DCTLib

If you apply binary search, you have $$\log_2(n)+O(1)$$ many comparisons. If you apply ternary search, you have $$ 2 \cdot \log_3(n) + O(1)$$ many comparisons, as in each step, you need to perform 2 comparisons to cut the search space into three parts. Now if you do the math, you can observe that: $$ 2 \cdot \log_3(n) + O(1) = 2 \cdot \frac{\log(2)}{\log(3)} \log_2(n)+ O(1) $$ Since we know that $2 \cdot \frac{\log(2)}{\log(3)} > 1$, we actually get more comparisons with ternary search.

By the way: $n$-ary search may make a lot of sense in case if comparisons are quite costly and can be parallelized, as then, parallel computers can be applied.

Note that argument can be generalized to $n$-ary search quite easily. You just need to show that the function $f(k) = (k-1) \cdot \frac{\log(2)}{\log(k)}$ is strictly monotone increasing for integer values of $k$.