Ternary search is worse than binary search?

Question

People usually ask the opposite of this question (Is ternary search is better than binary search?).

I really think it's worse (not in terms of both run at complexity of O(log n)). I'm really not good with the math, just pure intuition.

If we take an array of size n and use binary search, after the first comparison we have n/2 problem size, and after the 2nd comparison we have n/4 of the problem size.

With ternary search, the first loop run already makes 2 comparisons! And we're left with a problem size of n/3.

Am I right about this or am I missing something? The thing is in everything I read people usually take into account that the first loop run of ternary search is 1 compare which I think is wrong.

Answer 1

As a fun exercise, let's think about d-ary search, where you look at (d - 1) evenly-spaced elements of the array, then decide which of d different intervals to recursively descend into. If you use d-ary search, the size of the array remaining at each point will be n, n / d, n / d², n / d³, ..., n / d^k, ... . This means that there will be log_d n layers in the recursion. At each layer, you make exactly d - 1 comparisons. This means that the total number of comparisons made is (d - 1) log_d n. For any fixed value of d, this is O(log n), though the constant factor will be different.

With binary search, d = 2, and the number of comparisons will be (roughly) (2 - 1) log₂ n = log₂ n. For simplicity, let's write that as a natural logarithm by writing it as ln n / ln 2 = 1.443 ln n.

With ternary search, d = 3, and the number of comparisons will be (roughly) (3 - 1) log₃ n = 2 log₃ n. Writing this as a natural log, we get that this is 2 ln n / ln 3 = 1.820 ln n. Therefore, the number of comparisons in ternary search is indeed bigger than the number of comparisons in binary search, so you'd expect it to be slower than binary search. Indeed, as this article points out, that's what happens in practice.

Hope this helps!