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$.
