jsschools

Ternary Search

Finds the minimum or maximum of a unimodal function by dividing the search space into three parts and eliminating one third each iteration.

Spec ↗

Syntax

ternarySearch(lo, hi, f, eps?)

Parameters

NameTypeRequiredDescription
lo number Yes Lower bound of the search domain.
hi number Yes Upper bound of the search domain.
f (x: number) => number Yes A unimodal function — one that first decreases then increases (for minimum) or first increases then decreases (for maximum).
eps number No Precision threshold. Defaults to 1e-9. Iteration stops when hi - lo < eps.

Returns

number — The x-value where f achieves its minimum (or maximum).

Examples

// Find x that minimises f(x) = (x - 3)^2 + 2
function ternarySearch(lo, hi, f, eps = 1e-9) {
  while (hi - lo > eps) {
    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;
}

const f = x => (x - 3) ** 2 + 2;
const minX = ternarySearch(0, 10, f);
console.log(minX.toFixed(6));
console.log(f(minX).toFixed(6));
Output 
3.000000
2.000000

// Integer ternary search on a discrete unimodal array
function ternarySearchInt(arr) {
  let lo = 0, hi = arr.length - 1;
  while (hi - lo > 2) {
    const m1 = Math.floor(lo + (hi - lo) / 3);
    const m2 = Math.ceil(hi - (hi - lo) / 3);
    if (arr[m1] < arr[m2]) hi = m2;
    else lo = m1;
  }
  let best = lo;
  for (let i = lo + 1; i <= hi; i++) {
    if (arr[i] < arr[best]) best = i;
  }
  return best;
}

// Unimodal: decreasing then increasing
const arr = [10, 7, 3, 1, 4, 8, 15];
console.log(ternarySearchInt(arr)); // minimum at index 3
Output 
3

Notes

| Case | Time | Space | |---------|----------|-------| | Best | O(1) | O(1) | | Average | O(log n) | O(1) | | Worst | O(log n) | O(1) | Ternary search eliminates 1/3 of the range each step, giving log_(3/2)(n) iterations — slightly more than binary search's log_2(n) — so binary search is preferred when the predicate is monotone. Ternary search is the right tool when the objective is **unimodal** (single peak/valley). For discrete integer arrays, handle the last 2–3 elements with a linear scan to avoid off-by-one. Not applicable to multimodal functions.

See also