Ternary Search

Binary search requires a monotone function — values only go up, or only go down. Ternary search works on unimodal functions: values decrease to some peak (or valley) and then increase, with no second peak. The goal is to find that extremum.

Unimodal Functions

A function f is unimodal on [lo, hi] if there exists some peak p such that f is strictly increasing on [lo, p] and strictly decreasing on [p, hi] (or the mirror for a valley). Comparing f(m1) and f(m2) at two midpoints tells you which third of the range cannot contain the extremum.

Algorithm

Divide [lo, hi] into thirds with two midpoints m1 and m2:

• If f(m1) < f(m2) — the peak is in [m1, hi], so set lo = m1 + 1.
• If f(m1) > f(m2) — the peak is in [lo, m2], so set hi = m2 - 1.
• If f(m1) === f(m2) — the peak is in [m1, m2]; shrink both ends.

Each iteration discards at least one third of the range.

// Find the index of the maximum in a unimodal array (discrete ternary search)
function ternarySearchMax(arr) {
  let lo = 0;
  let hi = arr.length - 1;

  while (hi - lo > 2) {
    const third = Math.floor((hi - lo) / 3);
    const m1 = lo + third;
    const m2 = hi - third;

    if (arr[m1] < arr[m2]) {
      lo = m1 + 1; // peak is to the right of m1
    } else if (arr[m1] > arr[m2]) {
      hi = m2 - 1; // peak is to the left of m2
    } else {
      lo = m1 + 1; // equal — safely shrink both sides
      hi = m2 - 1;
    }
  }

  // Scan the remaining tiny window (at most 3 elements)
  let maxIdx = lo;
  for (let i = lo + 1; i <= hi; i++) {
    if (arr[i] > arr[maxIdx]) maxIdx = i;
  }
  return maxIdx;
}

const values = [1, 3, 7, 12, 9, 5, 2];
ternarySearchMax(values); // 3  (arr[3] === 12)

Continuous Ternary Search

For continuous functions (e.g. finding the minimum of a convex curve), run the loop a fixed number of iterations instead of until lo > hi:

function ternarySearchMin(f, lo, hi, iterations = 200) {
  for (let i = 0; i < iterations; i++) {
    const m1 = lo + (hi - lo) / 3;
    const m2 = hi - (hi - lo) / 3;
    if (f(m1) < f(m2)) hi = m2;
    else               lo = m1;
  }
  return (lo + hi) / 2; // approximate minimum x
}

// Example: minimum of f(x) = (x - 4)^2
const x = ternarySearchMin((x) => (x - 4) ** 2, 0, 10);
Math.round(x); // 4

Complexity

Why Ternary Search Rarely Beats Binary Search in Practice

Ternary search makes 2 comparisons per iteration to discard one third. Binary search makes 1 comparison per iteration to discard one half.

Discarding one third in 2 comparisons is the same asymptotic rate as binary search discarding one half in 1 comparison — both are O(log n). Ternary search’s constant factor of 2 means it is slower in practice for most discrete problems. It shines specifically on continuous unimodal functions where computing f is expensive and you want the fewest function evaluations (in which case each “comparison” is actually two separate evaluations of an expensive function, and the log₃ base matters).

Up Next

Rotated sorted arrays break the standard binary search invariant — but a modified version can still find targets in O(log n).