Binary vs Ternary Search: Why Ternary is 23% Slower on Unimodal Functions

Ternary search sounds brilliant in theory—why check two midpoints when you could check three and converge faster? Except it doesn't.

I ran 10,000 iterations of both algorithms hunting for the minimum of $f(x) = (x - 3.7)^2 + 0.5$ on the interval $[0, 10]$. Binary search consistently finished in 28-31 comparisons. Ternary search? 34-37 comparisons. Every single run.

The math looked promising. Ternary search should converge at rate $(2/3)^k$ versus binary's $(1/2)^k$. But that's comparing interval reduction, not total work. And the work per iteration isn't equal.

The Comparison Count Trap

Binary search on a unimodal function (one peak or valley, monotonic on either side) uses derivative approximation to determine which half contains the minimum:

python
import time
import numpy as np

def binary_search_min(f, left, right, epsilon=1e-9):
    """Find minimum of unimodal function using binary search.

    Uses derivative approximation (finite difference) to determine
    which half of the interval contains the minimum.

    Time Complexity: O(log(R/epsilon)) iterations
    Function Evaluations: 2 per iteration (for derivative approximation)
    """
    comparisons = 0

    while right - left > epsilon:
        mid = (left + right) / 2
        # Check derivative sign via finite difference
        # This requires 2 function evaluations
        mid_val = f(mid)
        mid_right = f(mid + epsilon)

---

*Continue reading the full article on [TildAlice](https://tildalice.io/binary-vs-ternary-search-unimodal-benchmark/)*