Binary Search vs Ternary Search

Question

In terms of time and space complexity, is binary search better than ternary search?

Answer 1

Both have constant space, but big O time for Ternary Search is Log_3 N instead of Binary Search's Log_2 N which both come out to log(N) since log_b(N) = log_x(N)/log_x(b).

In practice Ternary Search isn't used because you have to do an extra comparison at each step, which in the general case leads to more comparisons overall. 2 * Log_3(N) comparisons vs Log_2(N) comparisons.

Answer 2

It probably depends on the data. If you have roughly equal numbers of less than, equal to, and greater than comparisons, then splitting the data three ways means the base of the logarithm is 3 rather than 2, which is better. But in practice a three-way comparison is more expensive than a 2-way comparison, so the extra cost of the three-way comparison probably isn't worth it in the general case.