Binary Search vs Ternary Search

Question

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

possible duplicate of [Why use binary search if there's ternary search?](http://stackoverflow.com/questions/3498382/why-use-binary-search-if-theres-ternary-search) — orlp, Sep 14 '15 at 19:33
This really depends on what you are trying to do, what are you trying to do? — Clarus, Sep 14 '15 at 19:33

Louis Ricci · Answer 1 · 2015-09-14T19:57:06.157

5

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.

edited Sep 14 '15 at 19:57

answered Sep 14 '15 at 19:39

Louis Ricci

20,804
5
48
62

1

But O(log_2 n)=O(log_3 n). – Nico Schertler Sep 14 '15 at 19:42
@NicoSchertler - They both have the same big Oh complexity log(N) but because Ternary Search requires more comparisons it's not used. In the real world Binary Search is less complex. – Louis Ricci Sep 14 '15 at 20:00

score 0 · Answer 2 · answered Sep 14 '15 at 20:24

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.

Binary Search vs Ternary Search

2 Answers2

Linked