This site's twelfth Searching entry answers the exact same question
its own sibling Ternary Search does — find the
peak of a unimodal sequence, one that strictly rises to a single
maximum and then strictly falls — with the same divide-and-discard shape and the same
O(log n) number of narrowing steps. What differs is how much each step costs. Ternary
search picks two new probes every iteration and throws both away once it decides which side to keep.
Golden-section search picks its two probes at the golden ratio's split point instead of thirds, which
has a property thirds doesn't: after discarding a side, one of the two surviving probes is
already sitting exactly where the next iteration would have put it anyway. Only the other one needs a
fresh evaluation. Same number of iterations, roughly half the evaluations per iteration after the
first — a real saving whenever evaluating a candidate is the expensive part, not the comparison
itself.
Same two 31-element tent-shaped presets Ternary Search's own demo uses — peak near center (index 15) and peak near edge (index 4) — loaded here unchanged so the two pages can be compared directly on identical input. Step through either one and watch the log call out which probe is reused from the previous step and which one is a fresh evaluation.
Same invariant ternary search keeps — if the peak exists, it's between lo and
hi — narrowed by the golden ratio's inverse, φ⁻¹ ≈ 0.618, instead of a
third. Given interior points c = hi - φ⁻¹·(hi-lo) and d = lo + φ⁻¹·(hi-lo):
if f(c) < f(d):
# peak can't be left of c — same argument ternary search makes for m1
lo = c
else:
# peak can't be right of d
hi = dThe golden ratio's defining property, φ⁻¹ = 1 - φ⁻², is what makes reuse possible:
discarding [lo, c) shrinks the range to exactly φ⁻¹ of its old width, and at
that new width, the point φ⁻¹ of the way in from the new lo lands exactly on
the old d — not approximately, exactly, for real-valued bounds. So the old d
becomes the new c with no new evaluation needed, and only the new d has to be
computed and evaluated fresh. Discarding the other side works symmetrically: the old c
becomes the new d. Ternary search's thirds have no equivalent identity — 1/3
isn't 1 - (1/3)² — so neither of its probes can ever be reused; both are strangers to the
new range on every single iteration.
function goldenMax(arr) {
const n = arr.length;
if (n === 0) return -1;
const invphi = (Math.sqrt(5) - 1) / 2; // φ⁻¹ ≈ 0.618
const idx = x => Math.max(0, Math.min(n - 1, Math.round(x)));
let lo = 0, hi = n - 1;
let c = hi - invphi * (hi - lo);
let d = lo + invphi * (hi - lo);
let fc = arr[idx(c)], fd = arr[idx(d)];
while (hi - lo > 3) {
if (fc < fd) {
lo = c; c = d; fc = fd;
d = lo + invphi * (hi - lo);
fd = arr[idx(d)];
} else {
hi = d; d = c; fd = fc;
c = hi - invphi * (hi - lo);
fc = arr[idx(c)];
}
}
// range is down to at most 4 candidates — finish with a direct scan
const loI = Math.floor(lo), hiI = Math.ceil(hi);
let best = loI;
for (let i = loI; i <= hiI; i++) {
if (arr[i] > arr[best]) best = i;
}
return best;
}Note what stays a float: lo, hi, c, and
d are never rounded except at the moment they're used to index into arr. That
choice isn't cosmetic — see the second pitfall below for what breaks when it's dropped.
Skipping the reuse defeats the entire point, without ever being wrong. The obvious
first draft recomputes both c and d from the formula every iteration, the
same shape as ternary search's own loop, just with φ⁻¹ in place of a third:
while (hi - lo > 3) {
const c = hi - invphi * (hi - lo);
const d = lo + invphi * (hi - lo);
if (arr[idx(c)] < arr[idx(d)]) lo = c; else hi = d;
}This version is never wrong — checked against 200,000 randomized unimodal arrays (lengths 4–303, random peak position), it finds the true peak every time, same as the reference implementation above. The problem is purely how much work it does to get there: across the same 200,000 trials it averages 20.5 array evaluations per search, against 14.4 for the version that reuses one probe per iteration — 42% more, because every iteration pays for two fresh evaluations instead of one. On the two Try It presets specifically, both versions reach the same 5 narrowing iterations, but the reused version needs only 11 (center) and 12 (edge) evaluations including the final scan, against 19 for ternary search on the identical arrays — the saving this page exists to demonstrate disappears completely if the reuse itself is skipped.
Rounding lo/hi/c/d to integers at every
step — not just at the final lookup — silently returns the wrong peak, and not rarely. It
looks like a harmless simplification, since array indices are integers anyway:
let lo = 0, hi = arr.length - 1;
let c = Math.round(hi - invphi * (hi - lo));
let d = Math.round(lo + invphi * (hi - lo));
let fc = arr[c], fd = arr[d];
while (hi - lo > 2) {
if (fc < fd) { lo = c; c = d; fc = fd; d = Math.round(lo + invphi * (hi - lo)); fd = arr[d]; }
else { hi = d; d = c; fd = fc; c = Math.round(hi - invphi * (hi - lo)); fc = arr[c]; }
}Sweeping every window width from 3 to 2,000, exactly one width ever makes Math.round(hi -
invphi*(hi-lo)) and Math.round(lo + invphi*(hi-lo)) land on the same integer:
width 4. At that width φ⁻¹·4 ≈ 2.472 rounds to 2 from both directions, so
c and d collide on the exact midpoint, fc and fd
come out equal, and the tie-break (else, since fc < fd is false) discards
a side — sometimes the side holding the true peak, with no error and no signal anything went wrong.
Concretely: on the 15-element tent 70, 75, 80, 85, 90, 95, 100, 95, 90, 85, 80, 75, 70, 65,
60 (peak 100 at index 6), this integer-rounded version narrows to lo=3, hi=7, computes
c=5 and d=5 — both reading 95 — takes the else branch, and
finishes scanning [3, 5]: best value found is 95 at index 5, never revisiting index 6 at
all. Run across the same 200,000-trial sweep used above, this version returns the wrong index
28.7% of the time. The float reference implementation never hits this, because
c and d stay at their exact golden-ratio positions — fractions apart, not
merged — until the loop has already exited and only the final scan needs an integer index.
O(log n) narrowing steps, same order as ternary search's log₃⁄₂(n),
just with a smaller base (φ⁻¹ ≈ 0.618 < 2/3), so golden-section search actually needs
fewer iterations to reach the same final window — 5 against ternary search's 8 on both Try It
presets, verified by running both algorithms against the identical 31-element arrays. Combined with
one evaluation per iteration instead of two, the total evaluation count drops from 19 to 11–12 on
those same arrays, roughly the 40% saving the 200,000-trial averages above confirm in general. That
gap only matters when evaluating a candidate is the expensive step — a real function call, a
simulation, a rendered frame — not when the array is already sitting in memory and indexing it is
free, in which case the extra bookkeeping golden-section search needs to track c and
d as floats isn't worth it over ternary search's simpler integer-only loop. See Choosing a Search Algorithm for how all twelve
Searching entries stack up side by side.