comparison of binary and ternary search

Question

Considering this post which says: "big O time for Ternary Search is Log_3 N instead of Binary Search's Log_2 N"

this should be because classical ternary search would require 3 comparisons instead of two, but would this implementation be any more inefficient than a binary search?

#!/usr/bin/python3

List = sorted([1,3,5,6,87,9,56, 0])
print("The list is: {}".format(List))

def ternary_search(L, R, search):
    """iterative ternary search"""

    if L > R:
        L, R = R, L
    while L < R:

        mid1 = L + (R-L)//3
        mid2 = R - (R-L)//3

        if search == List[mid1]:
            L = R = mid1
        elif search == List[mid2]:
            L = R = mid2            
        elif search < List[mid1]:
            R = mid1
        elif search < List[mid2]:
            L = mid1
            R = mid2
        else:
            L = mid2

    if List[L] == search:
        print("search {} found at {}".format(List[L], L))
    else:
        print("search not found")


if __name__ == '__main__':
    ternary_search(0, len(List)-1, 6)

This implementation effectively takes only two comparison per iteration. So, ignoring the time taken to compute the mid points, wouldn't it be as effective as a binary search?

Then why not take this further to a n- ary search?

(Although, then the major concern of the search would be the number of midpoint calculations rather than the number of the comparisons, though I don't know if that's the correct answer).

Since **O(log_2 N) = O(log_3 N)**, the post you refer to makes no sense. The answer is correct, though. Binary search does fewer comparisons in the worst case if you do it right. — Matt Timmermans, Oct 15 '17 at 16:42
Possible duplicate of [Binary Search vs Ternary Search](https://stackoverflow.com/questions/32572355/binary-search-vs-ternary-search) — Matt Timmermans, Oct 15 '17 at 16:44
@MattTimmermans , I've pointed out above that the ternary search as above does only two comparisons per iteration, so, wouldn't that make it same in the worst case? — mathmaniage, Oct 16 '17 at 03:03
A binary search only needs to do one comparison per iteration. See: https://stackoverflow.com/questions/39416560/how-can-i-simplify-this-working-binary-search-code-in-c/39417165#39417165 . Also, you have done **4** comparisons, because **==** counts. — Matt Timmermans, Oct 16 '17 at 03:06
A ternary search could be faster. Although it does more comparisons per iteration, each iteration reduces the remaining search space more than does a single iteration of binary search, which results in fewer iterations. I'm not saying that it *would* be faster, just that it's conceivable that it *could* be. Asymptotically, though, the two structures have the same complexity. — Jim Mischel, Oct 16 '17 at 12:56

score 1 · Accepted Answer · answered Oct 18 '17 at 17:58

While both have logarithmic complexity, a ternary search will be faster than binary search for a large enough tree.

Though the binary search have 1 less comparison each node, it is deeper than Ternary search tree. For a tree of 100 million nodes, assuming both trees are properly balanced, depth of BST would be ~26, for ternary search tree it is ~16. Again, this speed-up will not be felt unless you have a very big tree.

The answer to your next question "why not take this further to a n-ary search?" is interesting. There are actually trees which take it further, for example b-tree and b+-tree. They are heavily used in database or file systems and can have 100-200 child nodes spawning from a parent.

Why? Because for these trees, you need to invoke an IO operation for every single node you access; which you are probably aware costs a lot, lot more than in memory operations your code performs. So although you'll now have to perform n-1 comparisons in each node, the cost of these in memory operations pales into comparison to the IO cost proportional to tree's depth.

As for in memory operations, remember that when you have a n-ary tree for n elements, you basically have an array, which has have O(n) search complexity, because all elements are now in same node. So, while increasing ary, at one point it stops being more efficient and starts actually harming performance.

So why do we always prefer BSt i.e 2-ary and not 3 or 4 or such? because it's lot simpler to implement. That's it really, no big mystery here.

comparison of binary and ternary search

1 Answers1