3

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.

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
Seth Keno
  • 679
  • 8
  • 16
  • If a comparison is 1 operation then : 1 + 1 = 2 = c = c * 1 therefore O(c * 1) = 1 – Logan Murphy Mar 18 '14 at 18:23
  • Just gotta love trinary logic: true + false + file_not_found. – Marc B Mar 18 '14 at 18:25
  • Related / possible duplicate - [Why use binary search if there's ternary search?](http://stackoverflow.com/q/3498382) – Bernhard Barker Mar 18 '14 at 18:27
  • But comparisons aren't everything. Cache coherency also comes into play. Searching a ternary tree will generally result in fewer cache misses, and those cache misses are much more expensive than a few extra comparisons. – Jim Mischel Mar 18 '14 at 22:13

1 Answers1

12

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 / d2, n / d3, ..., n / dk, ... . This means that there will be logd 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) logd 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) log2 n = log2 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) log3 n = 2 log3 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!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • 3
    You're overstating the number of comparisons in the ternary search slightly. `d-1` is the *maximum* number of comparisons in the worst case; on average, you would expect to need only `d/2` comparisons. – chepner Mar 18 '14 at 18:32
  • @chepner- That's a good point. I was thinking from a worst-case perspective rather than average-case perspective, so thanks for pointing that out! – templatetypedef Mar 18 '14 at 18:33
  • I agree with this analysis, however, there are cases where ternary search is better. http://www.pvk.ca/Blog/2012/07/30/binary-search-is-a-pathological-case-for-caches/ The pathological cache behavior mentioned in the article has to do with the fact that memory caches, as a rule, are not fully associative. As such, as single cache location can only hold cache lines from a small number of memory addresses. Because of that you can get terrible cache performance when binary searching an array that is a power of 2 in size. – davidmw Jul 09 '15 at 10:50