progress

~/problems / Search tricks / Ternary search

Peak of a unimodal function on reals

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

easy basics ~10 min

f is unimodal on [lo, hi] if it strictly increases to a single peak, then strictly decreases (the peak may sit at lo or hi).

Write argmax(f, lo: float, hi: float) -> float returning the x in [lo, hi] where f is largest, within 1e-6.

argmax(lambda x: -(x - 2.5) ** 2, 0.0, 10.0)   # about 2.5
argmax(lambda x: x, 0.0, 1.0)                  # about 1.0  (peak at the right edge)
argmax(math.sin, 0.0, math.pi)                 # about 1.5707963 (pi / 2)

lo < hi, hi - lo <= 10^6. You may call f at most 500 times (the tests count).

Show hint

take m1 = lo + (hi - lo) / 3 and m2 = hi - (hi - lo) / 3; if f(m1) < f(m2) the peak isn't in [lo, m1], so lo = m1, else hi = m2. Repeat about 100 times.

Topic: Ternary search. Maximize a unimodal function; or binary search on the slope.

0:00
Ctrl ' run · Ctrl ↵ submit
esc