Why use Binary Search if there’s ternary search?

I recently heard about ternary search in which we divide an array into 3 parts and compare. Here there will be two comparisons but it reduces the array to n/3. Why don’t people use this much?

By your logic then, n-ary should be the fastest. But if you think about it, n-ary is exactly equal to a regular iteration search (just iterating through the list 1 by 1, but in reverse order). First you select the last (or next to last) item in the list and compare that value to your comparison value. Then you remove that item from your list, and then choose the last item in the new list, which is just the next to last value in the array. Each time, you would only be eliminating 1 value at a time until you found your value.

Instead, you should think about it like this – how do I eliminate the most values from the list each iteration? In a binary search, you always eliminate half the list. In a ternary search, there is a possibility (33.33% chance, actually) that you can eliminate 2/3 of the list, but there is an even greater chance (66.66%) that you will only eliminate 1/3 of the list. in order to calculate O(n), you need to look at the worst case scenario, which is 1/3, less than 1/2. As you get closer and closer to n, it gets even worse.

Not only will the worst case scenario be improved with binary search, but your average time will be improved as well. Looking at expected value (what portion of the list can we remove on average), we use this formula:

(P\_lower)x(portion we can remove if lower)+(P\_higher)x(portion we can remove if higher) = E

For binary search, this is .5x.5 + .5x.5 = .5 (we always remove half the list). For ternary searches, this value is .666x.333 + .333x.666 = 0.44, or at each step, we will likely only remove 44% of the list, making it less efficient than the binary search, on average. This value peaks at 1/2 (half the list), and decreases the closer you get to n (reverse iteration) and 0 (regular iteration).

Also your CPU doesn’t support ternary logic as a single operation; it breaks ternary logic into several steps of binary logic. The most optimal code for the CPU is binary logic. If chips were common that supported ternary logic as a single operation, you’d be right.

A ternary search will still give you the same asymptotic complexity O(log n) search time, and adds complexity to the implementation. The same argument can be said for why you would not want a quad search or any other higher order.