Course contentsShow
← Computer Science
Lesson 820 of 2,87219. Searching and SelectionFree lesson

Ternary Search for Unimodal Functions

Use ternary search to find maxima or minima of unimodal functions by dividing search space into thirds.

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:

  1. Calculate two points: mid1 (at 1/3 of the range) and mid2 (at 2/3 of the range)
  2. Evaluate the function at both points
  3. For finding a maximum:
    • If f(mid1) < f(mid2), the peak must be to the right of mid1 (discard left third)
    • If f(mid1) > f(mid2), the peak must be to the left of mid2 (discard right third)
  4. 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.