Binary search does 5 operations

• Calculate mid: 3 operations (1 subtraction, 1 division by 2, 1 addition)
• Compare target with mid element: 1 comparison
• Update boundary (low or high): 1 assignment

Ternary search does 9 operations

• Calculate mid1 and mid2: 6 operations (2 subtractions, 2 divisions by 3, 2 additions/subtractions)
• Compare target/function values at mid1 and mid2: 2 comparisons
• Update boundaries (low, high, or both): 1 assignment

What is ternary search?

Ternary search is a type of search similar to binary search but instead of splitting the vector into 2 and checking which half the answer is in, it divides it into 3 parts and checks which third contains the answer.

So binary search is O(log₂ n) while ternary search is O(log₃ n).

But I'm here to prove ternary search is always slower.

Let's write log₃ using log₂.

(log₃ n) / (log₂ n) = (log n / log 3) / (log n / log 2)

(log n / log 3) / (log n / log 2) = (log 2) / (log 3)

(log 2) / (log 3) ≈ 0.6309297536...

So log₃ is almost 0.63 * log₂.

Since log₃ = 0.63...(infinite decimals) * log₂, we can round and conclude:

log₃ < 0.64 * log₂

Let's put it in our inequality:

9 * log₃ > 5 * log₂ -->

9 * log₂ * 0.64 > 5 * log₂

5.76 * log₂ > 5 * log₂ which is true

Since the growth ratio of log₃ to log₂ is less than 1, log₃ will increase more slowly, so ternary search, despite dividing into 3 parts, performs more operations per iteration and thus is always slower than binary search.

Also an interesting fact is that while the O of one is Log3 and the other is Log2, the log2 is faster than the log3.