~/problems
Problems
Basics first, then the classics, then company-style assessments. Every problem has tests you run right here; multi-level ones unlock as you go. See the roadmap.
Ternary search
Maximize a unimodal function; or binary search on the slope.
Notes
Recognise it when: a function first increases and then decreases (or the reverse) and you want its peak.
- On integers, prefer binary search on the slope:
if f(mid) < f(mid + 1): lo = mid + 1 else: hi = mid. - On reals, ternary search: evaluate at m1 = lo + (hi-lo)/3 and m2 = hi - (hi-lo)/3, then drop the worse third. Stop after a fixed number of iterations (100).
Gotchas: plateaus break ternary search on integers. It only works when the function is strictly unimodal.
6 problems
Advanced & competitive
Search tricks Ternary search, meet in the middle.
Ternary search
- Basics: peak of a unimodal function on reals basics easy
- When is the drone closest to the beacons? py · c++ · java easy
- Peak of a mountain array easy
- Find Peak Element medium
- Minimize a black-box convex function Uber medium
- When to leave the elevator Uber py · c++ · java medium