Ternary Search for Unimodal Functions
You'll learn how to find the maximum or minimum of a "hill-shaped" or "valley-shaped" function by cleverly dividing your search space into three parts instead of two.
What Is a Unimodal Function?
A unimodal function has a single peak (maximum) or valley (minimum). Think of climbing a smooth hill: as you walk, you go upward, reach the top, then go downward. There's only one summit, no smaller bumps along the way.
Binary search works great when you're looking for a specific value in sorted data. But what if you want to find where a function reaches its highest point? That's where ternary search shines.
How Ternary Search Works
Instead of splitting the search range into two halves, ternary search divides it into three equal parts using two midpoints:
- Calculate two points:
mid1(at 1/3 of the range) andmid2(at 2/3 of the range) - Evaluate the function at both points
- For finding a maximum:
- If
f(mid1) < f(mid2), the peak must be to the right ofmid1(discard left third) - If
f(mid1) > f(mid2), the peak must be to the left ofmid2(discard right third)
- If
- Repeat until the range is tiny
The Core Insight
You're not searching for a specific value—you're following the "slope" of the function. By comparing two points in the middle, you can tell which direction the peak lies and safely eliminate one-third of the search space.
Like binary search, each iteration reduces the problem size by a constant fraction, giving similar logarithmic efficiency.
Key Takeaway: Ternary search finds maxima or minima in unimodal functions by dividing the search space into thirds and eliminating the region that cannot contain the extremum, achieving logarithmic time complexity.