cf.completefrontend
SEARCHING & BINARY SEARCH · ADVANCED

Ternary search

Find the peak (or the lowest point) of a list or function that goes up and then down by comparing two inner points.

Time O(log n)Space O(1)3 practice problemsStep-through picture

The idea

Some data rises and then falls, like the height of a thrown ball over time, or a list such as [1, 3, 8, 12, 15, 11, 6, 2]. There is one peak, and we want to find it. The list is not sorted, so plain binary search does not apply. Ternary search does.

It picks two points inside the range, m1 and m2, about one third and two thirds of the way along. If the value at m1 is smaller than the value at m2, the curve is still rising at m1, so the peak can't be at or before m1. Otherwise, the peak can't be at or after m2. Either way, about a third of the range is thrown away.

The same idea works on smooth functions with real numbers, such as "which point on this line is closest to the mouse?". There you repeat a fixed number of times, say 100, and the range shrinks to a tiny width around the best point.

An everyday example

Finding the top of a hill in fog

You walk along a trail over a single hill in thick fog, and you want the highest point. You send two friends to two spots, one a third of the way along and one two thirds along, and each tells you their height. If the first friend is lower than the second, the top can't be behind the first friend, because the trail was still climbing there. So you forget the first third of the trail. Then you send them out again on what is left.

How the example maps to the code
In the exampleIn the code
The trail from start to endlow to high
The two friends' spotsm1 and m2
The first friend is lowervalues[m1] < values[m2]
Forget the trail up to the first friendlow = m1 + 1
Forget the trail from the second friend onhigh = m2 - 1

From the slow way to ternary search

  1. To find the biggest value in a list that rises and then falls, the obvious way scans every item and keeps the largest: n checks. That ignores the shape. In [2, 5, 9, 14, 20, 26, 31, 27, 18, 11, 6, 3], each item can tell you which side of the peak you are on, if you compare it with another one.
  2. One check at one index isn't enough. Knowing that values[5] is 26 says nothing about where the peak is. Two checks do help: compare the values at two indexes m1 < m2. If values[m1] < values[m2], the curve was still rising somewhere after m1, so the peak can't be at m1 or before it.
  3. If instead values[m1] >= values[m2], the curve was already falling by m2, so the peak can't be at m2 or after it. Placing m1 and m2 at one third and two thirds of the range means either result drops about a third of it, so each loop leaves about two thirds of the range.
  4. When three or fewer items are left, the range is too small to split into thirds, so just check those items one by one. Two probes at the thirds, drop the side that can't hold the peak, then a short scan at the end: that loop is ternary search.

How it works

  1. Set low and high to the ends of the range.
  2. While the range has more than three items, compute third = Math.floor((high - low) / 3), m1 = low + third, and m2 = high - third.
  3. If values[m1] < values[m2], the peak is after m1: set low = m1 + 1.
  4. Otherwise the peak is before m2: set high = m2 - 1.
  5. When three or fewer items are left, check them one by one and return the index of the largest.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function ternaryPeak(values) {
  2. let low = 0;
  3. let high = values.length - 1;
  4. while (high - low > 2) {
  5. const third = Math.floor((high - low) / 3);
  6. const m1 = low + third;
  7. const m2 = high - third;
  8. if (values[m1] < values[m2]) {
  9. low = m1 + 1;
  10. } else {
  11. high = m2 - 1;
  12. }
  13. }
  14. let best = low;
  15. for (let i = low + 1; i <= high; i++) {
  16. if (values[i] > values[best]) best = i;
  17. }
  18. return best;
  19. }

How fast it is

TimeO(log n)
Extra memoryO(1)

Each loop throws away about a third of the range, so the number of loops grows with the logarithm of n. Only a few indexes are stored.

  • Best caseO(log n)

    There is no early exit: even when the first probe lands on the peak, the loop keeps going until three items are left.

  • Average caseO(log n)

    Any single-peak list: each loop keeps about two thirds of the range.

  • Worst caseO(log n)

    About log base 1.5 of n loops, at most about 31 for a million items, with two reads per loop.

Common mistakes

  • Using it on data with flat parts, such as [1, 5, 5, 5, 5, 2]. When values[m1] equals values[m2] on a flat stretch, you can't tell which side the peak is on. Ternary search needs strict rises and falls.
  • Using it on data with more than one peak. It finds a peak, not always the highest one.
  • Looping while (low < high) with integer m1 and m2. When only two items are left, third is 0, so nothing moves and the loop never ends.
  • For real numbers, stopping when high - low is "small enough" with a tiny value like 1e-12. Rounding errors may keep the gap from ever getting that small. Loop a fixed number of times instead.

When to use it

Look for these clues in a problem:

  • The values go up and then down (or down and then up), with exactly one peak or dip.
  • The question asks for the maximum or minimum of a smooth function over a range of real numbers.
  • Words like "single-peaked", "unimodal", "bitonic", or "first increasing then decreasing".
  • You can compute the value at any point, but you can't see the whole curve at once.

Check yourself

Answer each one in your head first, then open it.

Why does ternary search read two values per loop instead of one?

One value alone doesn't say whether you are left or right of the peak. Comparing two values says which way the curve goes between them.

Why does the loop stop when high - low is 2?

With three or fewer items, third would be 0 and the probes would just sit on the range's ends. A short scan over at most three items is simpler and just as fast.

Is ternary search faster than binary search on the slope?

No. Both read two values per loop, but ternary search keeps two thirds of the range while the slope search keeps half. For a million items that is about 31 loops against 20.

Why does a flat stretch break it?

When values[m1] equals values[m2], the peak could be on either side, but the code always drops the right side. In [1, 2, 2, 2, 2, 9, 2] it drops the 9.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 3 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The promise is: the peak's index is somewhere from low to high. It holds at the start, when the range is the whole list. It relies on the list rising strictly to one peak and then falling strictly, with no flat stretches.

Each step keeps it. If values[m1] < values[m2], then m1 can't be at or after the peak, because from the peak onward every value is smaller than the one before, so values[m2] would be smaller. So the peak is after m1, and low = m1 + 1 is safe. If values[m1] >= values[m2], then m2 can't be at or before the peak, because up to the peak every value is bigger than the one before, so values[m2] would be bigger. So high = m2 - 1 is safe.

While more than three items remain, third is at least 1, so low or high moves by at least 2 and the loop ends. The final scan then checks every index still in the range, and by the promise the peak is among them, so the largest of them is the peak.

Going deeper

3 more ideas

Why throwing away a third is safe

Say the values rise strictly to one peak and then fall strictly. If values[m1] < values[m2], then m1 is on the rising side: if it were at or after the peak, everything to its right would be smaller. So the peak is to the right of m1. If values[m1] >= values[m2], the same reasoning shows m2 is on the falling side, so the peak is to the left of m2. Either way the peak stays inside low to high.

The version for real numbers

For a function f(x) on a range of real numbers, use m1 = low + (high - low) / 3 and m2 = high - (high - low) / 3 with no rounding, and set low = m1 or high = m2. Each step keeps two thirds of the range, so after 100 steps the range is (2/3)^100 of its first size, far smaller than any rounding error. Then return f((low + high) / 2). To find a lowest point instead, flip the comparison.

How long it takes, and a faster cousin

Each step keeps two thirds of the range, so the number of steps is about log base 1.5 of n, which is still O(log n). On a list of whole-number positions, binary search on the slope is a bit faster: compare values[mid] with values[mid + 1]. If the next one is bigger, the peak is to the right. Ternary search shines on real-number functions, where there is no "next item".

Work it by hand

Every step in a table, with why

Find the peak of a list of 12 numbers that rises to 31 and then falls.

values = [2, 5, 9, 14, 20, 26, 31, 27, 18, 11, 6, 3]

SteplowhighIndexes readValuesWhat happensWhy
1011m1 = 3, m2 = 814, 1814 < 18, so low = 4third is 3. The curve is still rising after index 3, so the peak is to its right. Indexes 0 to 3 are dropped.
2411m1 = 6, m2 = 931, 1131 >= 11, so high = 8third is 2. The value at m2 is lower, so the curve is falling there. Indexes 9 to 11 are dropped.
348m1 = 5, m2 = 726, 2726 < 27, so low = 6third is 1. Since 26 < 27, the peak is after index 5. Only indexes 6 to 8 are left.
468i = 727 vs 31Not bigger: best stays 6high - low is 2, so the loop ends. The scan starts with best = 6 and compares each later index with it.
568i = 818 vs 31Not bigger: best stays 6The last index in the range is smaller too, so the scan ends.

It returns 6, the index of 31, after 3 loops and 2 scan steps. On 12 items that saves little, but on a million items the loop runs at most about 31 times.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Ternary searchO(log n)O(1)The data is a function of real numbers with one peak or valley, where there is no "next item" to compare with.
Binary search on the slopeO(log n)O(1)The data is a list with whole-number positions. It needs fewer reads than ternary search.
Linear scanO(n)O(1)The list is small, has flat parts, or may have more than one peak. It is always correct.

Extra memory: O(1): low, high, third, m1, m2, and best.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Ternary search and the other approaches, on a scale where each line up is 10 times more steps.
  • Ternary search, Binary search on the slope O(log n)
  • Linear scan O(n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Ternary search31020
Binary search on the slope31020
Linear scan101,0001 million

Inputs that need care

5 tricky inputs
One, two, or three items
high - low is at most 2, so the loop never runs and the scan picks the largest. An empty list returns 0, which isn't a real index, so check values.length first if empty input is possible.
The peak at an end: [40, 31, 22, 9]
The list only falls. The comparison says values[m1] >= values[m2], high moves left, and the scan returns 0. A list that only rises returns its last index the same way.
A flat stretch: [1, 2, 2, 2, 2, 9, 2]
It returns 1, a 2, not the 9 at index 5. With values[m1] equal to values[m2], the code can't tell which side the peak is on and drops the wrong side. Use a full scan when flats are possible.
Two peaks: [5, 20, 4, 1, 7, 12, 3]
It returns 5, the 12, but the highest value is the 20 at index 1. Ternary search is only correct when there is exactly one peak.
A real-number function, like the distance from the mouse to points on a line
There are no indexes, so loop a fixed number of times, such as 100, and use m1 = low + (high - low) / 3 without rounding. Stopping at a tiny gap like 1e-12 can loop forever because of rounding.

Variations and follow-ups

Twists interviewers add

Binary search on the slope

For whole-number indexes, compare values[mid] with values[mid + 1]. If the next one is bigger, the peak is to the right, so low = mid + 1; otherwise high = mid. That halves the range per loop instead of keeping two thirds: about 20 loops for a million items, against about 31.

Golden-section search

Place the two probes at about 38.2% and 61.8% of the range. After each step, one old probe lands exactly where a new probe is needed, so each loop computes only one new value instead of two. This matters when each value is expensive to compute, like a full layout pass.

Lowest point of a valley

For data that falls and then rises, like cost against batch size, flip the test: if values[m1] > values[m2], the lowest point is after m1. Then keep the smallest value in the final scan.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "strictly increasing then strictly decreasing", "bitonic", "unimodal", "mountain", or "minimize a cost that falls and then rises" over a range of real numbers.
  • Say the rule out loud: "if the left probe is lower, the curve is still climbing after it, so the peak is to its right". Then say that it needs strict rises and falls, and what breaks on flat parts.
  • On an integer array, offer binary search on the slope as the better choice and say why: one comparison of neighbors halves the range. Keep ternary search for real-number functions.
  • The usual follow-up is "what if there might be several peaks?". Answer: ternary search can return a lower peak, as in [5, 20, 4, 1, 7, 12, 3]. Binary search on the slope still finds some local peak in O(log n), but finding the highest of several needs a full scan.

Where frontend code uses it

The same idea in real UI code
  • Snapping in a design tool: the distance from the cursor to points along a straight segment falls and then rises, so ternary search finds the closest point on the segment.
  • Tuning a single setting by measurement, such as an image quality setting that balances file size and visual score, when the score rises and then falls.
  • Finding the busiest moment in a traffic chart that has one clear peak, such as a launch-day spike.

Related algorithms