Loading…

easyBinary SearchSometimes asked

Ternary Search on a Unimodal Function

Q: How do you solve Ternary Search on a Unimodal Function using the Linear Scan approach?

When to use it: Say it first to fix correctness and the unimodality assumption, then point out it ignores the structure that lets us go logarithmic. The baseline simply evaluates the function everywhere and remembers the best. **The literal method.** Iterate over all `n` positions (or sample the real interval finely), evaluate `f`, and keep the maximum value and its index. **Why it's correct but wasteful.** It makes no assumption about shape, so it always works — but it throws away the one fact that matters here: the function has a single peak. With that structure, you don't need to look at every point; comparing a couple of interior points already tells you where the peak can't be. The linear scan ignores that and pays `O(n)` queries. **When it's still the right call.** If `n` is small, or you're unsure the function is truly unimodal, the scan is the safe choice — ternary search silently misbehaves on non-unimodal input, while the scan always returns the true global max of the sampled points. Time complexity: O(n). Space complexity: O(1).

Binary Search · 15 of 16 · 10 min

You are given access to a unimodal function f over an index range [0, n−1] (or a real interval [lo, hi]): f strictly increases up to a single peak, then strictly decreases. Return the position of the maximum (the peak) and/or its value.

For a unimodal valley (strictly decreasing then increasing), return the minimum instead.

In plain English

There's no value to match — you're hunting the single turning point of a curve that goes up then down. Because the function has just one peak, comparing the heights at two interior points reveals which side of them the peak lies on, so you can safely discard a chunk of the range each step, mirroring binary search but on the function's slope rather than on a sorted value.

Examples

Example 1

Input: arr = [1, 3, 8, 12, 4, 2] (mountain), find peak value
Output: 12 (at index 3)
Note: Strictly increases to 12, then decreases. Two interior probes converge on index 3.

Example 2

Input: f(x) = -(x-2)² + 5 over [0, 5], find max
Output: x = 2, f = 5
Note: Concave parabola; ternary search narrows the real interval around x = 2.

Example 3

Input: arr = [9, 7, 4, 6, 10] is NOT unimodal
Output: undefined / wrong
Note: Two valleys/peaks violate the precondition — ternary search would return a meaningless point.

Constraints

f is strictly unimodal over the search range (exactly one turning point, no plateaus)
1 ≤ n ≤ 10⁹ for the discrete version; reals use a fixed iteration count
Evaluating f is O(1) (or counted as one query)
For arrays, the peak is strictly greater than its neighbors

Clarifying questions4First question: Is the function guaranteed strictly unimodal?Explore questions

Q1.Is the function guaranteed strictly unimodal?
Critical. Ternary search is only correct with exactly one peak and no flat regions. If there are plateaus or multiple peaks, the comparison can point the wrong way.
Q2.Maximum or minimum?
Either — the structure is identical; you just flip the comparison direction. Confirm which extremum is wanted.
Q3.Discrete indices or a real interval?
Decides the stopping rule: integers stop at a tiny window (and scan it); reals iterate a fixed number of times or until within epsilon.
Q4.Is querying f expensive?
If each evaluation is costly, prefer the f(mid) vs f(mid+1) binary search — it makes one comparison per step instead of two probes.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Find the peak (or valley) of a unimodal function — one that strictly increases then strictly decreases (or the reverse). You can't binary-search on the value, but you can binary-search on the slope: probe two interior points m1 < m2. If f(m1) < f(m2) the maximum is to the right of m1, so discard [lo, m1]; otherwise discard [m2, hi]. Each step removes a third of the range, giving O(log n) probes. A cleaner equivalent keeps a binary search comparing f(mid) with f(mid+1).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognize that an extremum (not a target) over a unimodal range is still a logarithmic search, and whether you can justify which side to discard from a two-point comparison.

Where candidates slip

Applying ternary/binary search to a function that isn't strictly unimodal (plateaus or multiple peaks), or discarding the wrong third by mixing up the max vs min comparison direction.

How to stand out

State the unimodality precondition explicitly, derive the discard rule from 'which way is uphill', and mention the cleaner f(mid) vs f(mid+1) slope binary search for the discrete case.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Linear Scan	`O(n)`	`O(1)`	Say it first to fix correctness and the unimodality assumption, then point out it ignores the structure that lets us go logarithmic.	Read
2	Ternary Search (Optimal)Optimal	`O(log n)`	`O(1)`	The intended answer. Frame it as binary search on the slope and state the unimodality precondition up front.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewProbe m1 < m2 inside [lo, hi]f(m1) < f(m2)? (maximum)Yes, still climbingNo, already descendingExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Linear Scan

TimeO(n)SpaceO(1)

Say it first to fix correctness and the unimodality assumption, then point out it ignores the structure that lets us go logarithmic.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Walk every position and keep the best value seen. For a peak, track the running maximum and its index.

2Hint 2Explore hint

This works for any function, unimodal or not — but it never uses the single-peak structure.

3Hint 3Explore hint

n evaluations of f. If n is large or f is expensive, this is the cost we want to cut to O(log n).

A · Core idea

The baseline simply evaluates the function everywhere and remembers the best.

The literal method. Iterate over all n positions (or sample the real interval finely), evaluate f, and keep the maximum value and its index.

Why it's correct but wasteful. It makes no assumption about shape, so it always works — but it throws away the one fact that matters here: the function has a single peak. With that structure, you don't need to look at every point; comparing a couple of interior points already tells you where the peak can't be. The linear scan ignores that and pays O(n) queries.

When it's still the right call. If n is small, or you're unsure the function is truly unimodal, the scan is the safe choice — ternary search silently misbehaves on non-unimodal input, while the scan always returns the true global max of the sampled points.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

arr = [1, 3, 8, 12, 4, 2]

Array state

i=3

12 is the new best

[0]

[1]

[2]

i ↓

[3]

[4]

[5]

Current pointerResolved stateNot processed

Final result12 at index 3

C · Code with teaching comments

Reference implementation previewpublic class LinearPeak { public int peakIndex(int[] arr) { int best = 0; for (int i = 1; i < arr.length; i++) { if (arr[i] > arr[best]) best = i;Explore the full code

solution.javaJava

Linear Scan — reference

1 teaching note

1
public class LinearPeak {
2
    public int peakIndex(int[] arr) {
3
        int best = 0;
4
        for (int i = 1; i < arr.length; i++) {
5
            // Track the running maximum index — works for any array, ignores
6
            // unimodality.
7
            if (arr[i] > arr[best]) best = i;
8
        }
9
        return best;
10
    }
11
 
12
    public static void main(String[] args) {
13
        System.out.println(new LinearPeak().peakIndex(new int[]{1, 3, 8, 12, 4, 2}));
14
    }
15
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.15 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

The scan's O(n) cost comes entirely from not using unimodality. The whole optimization is to convert 'where is the max?' into repeated 'which way is uphill?' questions, each of which eliminates a fraction of the range.

ComplexityO(n) time, O(1) space — One pass over n positions, one f-evaluation each → O(n). Constant bookkeeping → O(1) space.

E · Edge cases and pitfalls3Treating O(n) as fine when n is 10⁹ or f is expensive.Explore edge cases

Pitfalls

Treating O(n) as fine when n is 10⁹ or f is expensive.
Assuming the scan needs unimodality — it doesn't, which is exactly why it's slower.
Comparing values instead of indices when the peak index is what's asked.

03.2

Approach 2 of 2 · Optimal

Ternary Search (Optimal)

TimeO(log n)SpaceO(1)

The intended answer. Frame it as binary search on the slope and state the unimodality precondition up front.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You can't compare f to a target — there isn't one. But you can compare f at two interior points. If the function is rising between them, the peak is to the right; if falling, the peak is to the left.

2Hint 2Explore hint

Split [lo, hi] into thirds with m1 = lo + (hi-lo)/3 and m2 = hi - (hi-lo)/3. Compare f(m1) and f(m2) to discard one outer third each step.

3Hint 3Explore hint

For integers, a cleaner variant binary-searches by comparing f(mid) with f(mid+1): if f(mid) < f(mid+1) the peak is to the right (lo = mid+1), else to the left (hi = mid).

A · Core idea

Ternary search locates the extremum of a unimodal function by repeatedly asking which direction is uphill.

Why you can't binary-search the value. Ordinary binary search needs a sorted/monotone relationship to a target. Here the values rise then fall, and there's no target — you want the turning point. So instead of comparing f(mid) to a target, you compare the function at two points to read its slope.

The two-probe step. Pick interior points m1 = lo + (hi−lo)/3 and m2 = hi − (hi−lo)/3, so m1 < m2. Evaluate both. For a maximum:

If f(m1) < f(m2), the function is still climbing as you go from m1 to m2, which means the peak lies to the right of m1. Discard [lo, m1] by setting lo = m1 + 1.
Otherwise (f(m1) >= f(m2)), you're already on the descending side by m2, so the peak is to the left of m2. Discard [m2, hi] by setting hi = m2 − 1.

Either way you throw away roughly a third of the range. Repeat until the window is tiny, then take the best point in it. For a minimum, flip both comparisons.

The cleaner discrete variant. On integer indices, two probes per step invite off-by-one and rounding bugs. A simpler equivalent is a binary search on the slope: take mid = (lo + hi) / 2 and compare f(mid) with f(mid+1). If f(mid) < f(mid+1) the slope is positive, so the peak is to the right: lo = mid + 1. Otherwise the peak is at mid or to its left: hi = mid. When lo == hi, that index is the peak. This halves the range each step with a single comparison and no thirds arithmetic — it's the version to prefer for arrays.

Real intervals. With continuous x, you can't reach exact equality. Iterate a fixed number of times (about 100–200 doublings of precision) or until hi − lo < epsilon, then report the midpoint. Never loop on f(m1) == f(m2) exactly — floating point won't cooperate.

The non-negotiable precondition. All of this assumes strict unimodality. If the function has a flat stretch, f(m1) can equal f(m2) with the peak on either side, and the discard rule has no basis. If there are multiple peaks, you may converge to the wrong one. State this assumption out loud — it's the thing interviewers probe.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

arr = [1, 3, 8, 12, 4, 2], find peak via f(mid) vs f(mid+1)

Array state

lo=0,hi=5,mid=2

8 < 12 → go right

[0]

[1]

mid ↓

[2]

[3]

[4]

hi ↓

[5]

Current pointerResolved stateNot processed

Final result12 at index 3

C · Code with teaching comments

solution.javaJava

Ternary Search (Optimal) — optimal

5 teaching notes

1
public class TernarySearch {
2
    // Discrete peak via slope binary search (preferred for arrays).
3
    public int peakIndex(int[] arr) {
4
        int lo = 0, hi = arr.length - 1;
5
        while (lo < hi) {
6
            int mid = lo + (hi - lo) / 2;
7
            // Positive slope between mid and mid+1 → the peak is strictly to the right.
8
            if (arr[mid] < arr[mid + 1]) {
9
                // Safe to discard everything up to and including mid.
10
                lo = mid + 1; // still climbing → peak to the right
11
            } else {
12
                // mid could be the peak, so keep it in the window.
13
                hi = mid;     // descending → peak at mid or left
14
            }
15
        }
16
        return lo;
17
    }
18
 
19
    // Classic ternary search on a real unimodal function (maximize).
20
    public double argmax(java.util.function.DoubleUnaryOperator f, double lo, double hi) {
21
        for (int iter = 0; iter < 200; iter++) {
22
            // Left interior probe at the one-third mark for the real-valued version.
23
            double m1 = lo + (hi - lo) / 3.0;
24
            double m2 = hi - (hi - lo) / 3.0;
25
            if (f.applyAsDouble(m1) < f.applyAsDouble(m2)) {
26
                lo = m1;
27
            } else {
28
                hi = m2;
29
            }
30
        }
31
        return (lo + hi) / 2.0;
32
    }
33
 
34
    public static void main(String[] args) {
35
        TernarySearch ts = new TernarySearch();
36
        System.out.println(ts.peakIndex(new int[]{1, 3, 8, 12, 4, 2}));
37
        System.out.printf("%.4f%n", ts.argmax(x -> -(x - 2) * (x - 2) + 5, 0, 5));
38
    }
39
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.39 lines

D · Why it works and complexityO(log n) timeO(1) spaceOpen the invariant and proofExplore the proof

Binary search exploits monotonicity to halve a search for a value; ternary search exploits unimodality to shrink a search for an extremum. Both reduce the range by a constant factor per step — the only difference is that here each comparison reads the slope (is it going up or down?) rather than checking against a target. Seeing that 'slope sign' is itself monotone over a unimodal range is what lets the simpler binary-search-on-f(mid)-vs-f(mid+1) work.

ComplexityO(log n) time, O(1) space — Each step removes about a third of the range (ternary) or half (the slope binary search), so the number of iterations is O(log n). Each iteration does O(1) f-evaluations → O(log n) total queries, O(1) extra space.

E · Edge cases and pitfalls7peak at the boundary [5,4,3,2,1] — Slope is always falling → converges to index 0; only valid if treated as a monotone-unimodal edge.Explore edge cases

Edge cases handled

peak at the boundary [5,4,3,2,1]Slope is always falling → converges to index 0; only valid if treated as a monotone-unimodal edge.
two-element array [2, 5]mid=0, arr[0]<arr[1] → lo=1 → peak index 1.
real function with very flat topStill converges near the max, but precision is limited; widen the iteration count if needed.

Pitfalls

Using ternary search on a non-unimodal or plateaued function — the discard rule becomes invalid.
Flipping the comparison direction (max vs min) and converging on the wrong extremum.
Looping until f(m1) == f(m2) on reals — float equality may never hold; iterate a fixed count.
Off-by-one in the two-probe integer version — prefer the f(mid) vs f(mid+1) form.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic class TernarySearch { // Discrete peak via slope binary search (preferred for arrays). public int peakIndex(int[] arr) { int lo = 0, hi = arr.length - 1; while (lo < hi) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

public class TernarySearch {
    // Discrete peak via slope binary search (preferred for arrays).
    public int peakIndex(int[] arr) {
        int lo = 0, hi = arr.length - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (arr[mid] < arr[mid + 1]) {
                lo = mid + 1; // still climbing → peak to the right
            } else {
                hi = mid;     // descending → peak at mid or left
            }
        }
        return lo;
    }

// Classic ternary search on a real unimodal function (maximize).
    public double argmax(java.util.function.DoubleUnaryOperator f, double lo, double hi) {
        for (int iter = 0; iter < 200; iter++) {
            double m1 = lo + (hi - lo) / 3.0;
            double m2 = hi - (hi - lo) / 3.0;
            if (f.applyAsDouble(m1) < f.applyAsDouble(m2)) {
                lo = m1;
            } else {
                hi = m2;
            }
        }
        return (lo + hi) / 2.0;
    }

public static void main(String[] args) {
        TernarySearch ts = new TernarySearch();
        System.out.println(ts.peakIndex(new int[]{1, 3, 8, 12, 4, 2}));
        System.out.printf("%.4f%n", ts.argmax(x -> -(x - 2) * (x - 2) + 5, 0, 5));
    }
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Assuming unimodality that isn't there

If the function has two peaks or a flat region, comparing two probes can point toward the wrong region, and ternary search converges to a non-global point. Verify the precondition first.

Explore the code comparison

Don't write this

# arr = [9, 7, 4, 6, 10] has two 'uphill' directions
idx = peak_index(arr)   # meaningless: not unimodal

Write this instead

# Ensure strictly-up-then-down before using ternary search;
# otherwise fall back to a linear scan.

Wrong discard direction for max vs min

For a maximum, f(m1) < f(m2) means go right. For a minimum the logic inverts. Copy-pasting the max version to find a min silently returns the wrong extremum.

Explore the code comparison

Don't write this

# finding a MIN but using the MAX comparison
if f(m1) < f(m2):
    lo = m1   # wrong for a minimum

Write this instead

# minimum: keep the side with the smaller value
if f(m1) < f(m2):
    hi = m2
else:
    lo = m1

Looping on float equality

On real intervals f(m1) == f(m2) may never become exactly true, so a while loop on equality can spin forever. Use a fixed iteration count or an epsilon width.

Explore the code comparison

Don't write this

while f(m1) != f(m2):   # may never terminate on floats
    ...

Write this instead

for _ in range(200):    # fixed iterations -> well within precision
    ...

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Binary search on the derivative's sign over a unimodal range

Code pattern to memorize

MAX of unimodal:
while hi - lo > 2:
    m1 = lo + (hi - lo) / 3
    m2 = hi - (hi - lo) / 3
    if f(m1) < f(m2): lo = m1 + 1   # peak is right of m1
    else: hi = m2 - 1               # peak is left of m2
answer = best f over [lo..hi]

DISCRETE shortcut: compare f(mid) vs f(mid+1) to decide which half holds the peak.

Rules to remember

1The function must be strictly unimodal — one peak (or one valley), no flat plateaus. Ternary search breaks on flats because f(m1) == f(m2) gives no direction.
2You're searching on the shape (slope), not the value — there's no target to match, you're locating the turning point.
3For a maximum: f(m1) < f(m2) ⇒ still climbing, discard the left third; else discard the right third. Flip both comparisons for a minimum.
4On integers, stop when the window is tiny (≤ 2–3 elements) and scan the rest, or use the f(mid) vs f(mid+1) slope test to avoid rounding traps.
5On reals, iterate a fixed number of times (e.g. ~100/200) or until the interval is within epsilon — don't loop on exact equality.

Use this pattern when

Optimize a single-peaked / single-valley function (maximize or minimize)
Peak in a bitonic / mountain array
Geometry: minimize distance to a point along a parametrized path
Any cost function known to be convex/concave over the search range

Choose another pattern when

Function is monotonic (only increasing or only decreasing) → plain binary search, not ternary
Function has multiple peaks / not unimodal → ternary search gives a wrong local answer
Plateaus exist (equal values over a stretch) → the comparison can't pick a side; rethink the model
You're matching a target value, not finding an extremum → ordinary binary search

Interview takeaway

Ternary search is binary search applied to the *slope* of a unimodal function: each comparison of two interior probes tells you which way is uphill, letting you throw away a constant fraction of the range every step for O(log n) convergence to the extremum.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternTernary search / binary-search-on-slope. Recognise it whenever you must optimize a single-peaked or single-valley function: probe the slope, discard a constant fraction, converge in O(log n). For discrete arrays, the f(mid) vs f(mid+1) form is the cleaner sibling.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Peak Index in a Mountain Array
Coming soon
Exactly the discrete slope binary search — compare arr[mid] with arr[mid+1].
Find Minimum in Rotated Sorted Array
A different shape, but the same 'compare to a neighbor/endpoint to pick a half' idea.
Minimize a Convex Cost over an Integer Range
Coming soon
Ternary search on the integer index, then check the final tiny window exhaustively.
Geometric Min-Distance Along a Path
Coming soon
Distance to a point along a straight segment is unimodal — ternary search the parameter t.

←

Floor and Ceil in a Sorted Array

Continue · Next problem

Pairs

easyBinary SearchSometimes asked

Ternary Search on a Unimodal Function

Binary Search · 15 of 16 · 10 min

For a unimodal valley (strictly decreasing then increasing), return the minimum instead.

In plain English

Examples

Example 1

Input: arr = [1, 3, 8, 12, 4, 2] (mountain), find peak value
Output: 12 (at index 3)
Note: Strictly increases to 12, then decreases. Two interior probes converge on index 3.

Example 2

Input: f(x) = -(x-2)² + 5 over [0, 5], find max
Output: x = 2, f = 5
Note: Concave parabola; ternary search narrows the real interval around x = 2.

Example 3

Input: arr = [9, 7, 4, 6, 10] is NOT unimodal
Output: undefined / wrong
Note: Two valleys/peaks violate the precondition — ternary search would return a meaningless point.

Constraints

f is strictly unimodal over the search range (exactly one turning point, no plateaus)
1 ≤ n ≤ 10⁹ for the discrete version; reals use a fixed iteration count
Evaluating f is O(1) (or counted as one query)
For arrays, the peak is strictly greater than its neighbors

Clarifying questions4First question: Is the function guaranteed strictly unimodal?Explore questions

Q1.Is the function guaranteed strictly unimodal?
Critical. Ternary search is only correct with exactly one peak and no flat regions. If there are plateaus or multiple peaks, the comparison can point the wrong way.
Q2.Maximum or minimum?
Either — the structure is identical; you just flip the comparison direction. Confirm which extremum is wanted.
Q3.Discrete indices or a real interval?
Decides the stopping rule: integers stop at a tiny window (and scan it); reals iterate a fixed number of times or until within epsilon.
Q4.Is querying f expensive?
If each evaluation is costly, prefer the f(mid) vs f(mid+1) binary search — it makes one comparison per step instead of two probes.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognize that an extremum (not a target) over a unimodal range is still a logarithmic search, and whether you can justify which side to discard from a two-point comparison.

Where candidates slip

Applying ternary/binary search to a function that isn't strictly unimodal (plateaus or multiple peaks), or discarding the wrong third by mixing up the max vs min comparison direction.

How to stand out

State the unimodality precondition explicitly, derive the discard rule from 'which way is uphill', and mention the cleaner f(mid) vs f(mid+1) slope binary search for the discrete case.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Linear Scan	`O(n)`	`O(1)`	Say it first to fix correctness and the unimodality assumption, then point out it ignores the structure that lets us go logarithmic.	Read
2	Ternary Search (Optimal)Optimal	`O(log n)`	`O(1)`	The intended answer. Frame it as binary search on the slope and state the unimodality precondition up front.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Linear Scan

TimeO(n)SpaceO(1)

Say it first to fix correctness and the unimodality assumption, then point out it ignores the structure that lets us go logarithmic.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Walk every position and keep the best value seen. For a peak, track the running maximum and its index.

2Hint 2Explore hint

This works for any function, unimodal or not — but it never uses the single-peak structure.

3Hint 3Explore hint

n evaluations of f. If n is large or f is expensive, this is the cost we want to cut to O(log n).

A · Core idea

The baseline simply evaluates the function everywhere and remembers the best.

The literal method. Iterate over all n positions (or sample the real interval finely), evaluate f, and keep the maximum value and its index.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

arr = [1, 3, 8, 12, 4, 2]

Array state

i=3

12 is the new best

[0]

[1]

[2]

i ↓

[3]

[4]

[5]

Current pointerResolved stateNot processed

Final result12 at index 3

C · Code with teaching comments

Reference implementation previewpublic class LinearPeak { public int peakIndex(int[] arr) { int best = 0; for (int i = 1; i < arr.length; i++) { if (arr[i] > arr[best]) best = i;Explore the full code

solution.javaJava

Linear Scan — reference

1 teaching note

1
public class LinearPeak {
2
    public int peakIndex(int[] arr) {
3
        int best = 0;
4
        for (int i = 1; i < arr.length; i++) {
5
            // Track the running maximum index — works for any array, ignores
6
            // unimodality.
7
            if (arr[i] > arr[best]) best = i;
8
        }
9
        return best;
10
    }
11
 
12
    public static void main(String[] args) {
13
        System.out.println(new LinearPeak().peakIndex(new int[]{1, 3, 8, 12, 4, 2}));
14
    }
15
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.15 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(1) space — One pass over n positions, one f-evaluation each → O(n). Constant bookkeeping → O(1) space.

E · Edge cases and pitfalls3Treating O(n) as fine when n is 10⁹ or f is expensive.Explore edge cases

Pitfalls

Treating O(n) as fine when n is 10⁹ or f is expensive.
Assuming the scan needs unimodality — it doesn't, which is exactly why it's slower.
Comparing values instead of indices when the peak index is what's asked.

03.2

Approach 2 of 2 · Optimal

Ternary Search (Optimal)

TimeO(log n)SpaceO(1)

The intended answer. Frame it as binary search on the slope and state the unimodality precondition up front.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

2Hint 2Explore hint

Split [lo, hi] into thirds with m1 = lo + (hi-lo)/3 and m2 = hi - (hi-lo)/3. Compare f(m1) and f(m2) to discard one outer third each step.

3Hint 3Explore hint

For integers, a cleaner variant binary-searches by comparing f(mid) with f(mid+1): if f(mid) < f(mid+1) the peak is to the right (lo = mid+1), else to the left (hi = mid).

A · Core idea

Ternary search locates the extremum of a unimodal function by repeatedly asking which direction is uphill.

The two-probe step. Pick interior points m1 = lo + (hi−lo)/3 and m2 = hi − (hi−lo)/3, so m1 < m2. Evaluate both. For a maximum:

If f(m1) < f(m2), the function is still climbing as you go from m1 to m2, which means the peak lies to the right of m1. Discard [lo, m1] by setting lo = m1 + 1.
Otherwise (f(m1) >= f(m2)), you're already on the descending side by m2, so the peak is to the left of m2. Discard [m2, hi] by setting hi = m2 − 1.

Either way you throw away roughly a third of the range. Repeat until the window is tiny, then take the best point in it. For a minimum, flip both comparisons.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

arr = [1, 3, 8, 12, 4, 2], find peak via f(mid) vs f(mid+1)

Array state

lo=0,hi=5,mid=2

8 < 12 → go right

[0]

[1]

mid ↓

[2]

[3]

[4]

hi ↓

[5]

Current pointerResolved stateNot processed

Final result12 at index 3

C · Code with teaching comments

solution.javaJava

Ternary Search (Optimal) — optimal

5 teaching notes

1
public class TernarySearch {
2
    // Discrete peak via slope binary search (preferred for arrays).
3
    public int peakIndex(int[] arr) {
4
        int lo = 0, hi = arr.length - 1;
5
        while (lo < hi) {
6
            int mid = lo + (hi - lo) / 2;
7
            // Positive slope between mid and mid+1 → the peak is strictly to the right.
8
            if (arr[mid] < arr[mid + 1]) {
9
                // Safe to discard everything up to and including mid.
10
                lo = mid + 1; // still climbing → peak to the right
11
            } else {
12
                // mid could be the peak, so keep it in the window.
13
                hi = mid;     // descending → peak at mid or left
14
            }
15
        }
16
        return lo;
17
    }
18
 
19
    // Classic ternary search on a real unimodal function (maximize).
20
    public double argmax(java.util.function.DoubleUnaryOperator f, double lo, double hi) {
21
        for (int iter = 0; iter < 200; iter++) {
22
            // Left interior probe at the one-third mark for the real-valued version.
23
            double m1 = lo + (hi - lo) / 3.0;
24
            double m2 = hi - (hi - lo) / 3.0;
25
            if (f.applyAsDouble(m1) < f.applyAsDouble(m2)) {
26
                lo = m1;
27
            } else {
28
                hi = m2;
29
            }
30
        }
31
        return (lo + hi) / 2.0;
32
    }
33
 
34
    public static void main(String[] args) {
35
        TernarySearch ts = new TernarySearch();
36
        System.out.println(ts.peakIndex(new int[]{1, 3, 8, 12, 4, 2}));
37
        System.out.printf("%.4f%n", ts.argmax(x -> -(x - 2) * (x - 2) + 5, 0, 5));
38
    }
39
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.39 lines

D · Why it works and complexityO(log n) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7peak at the boundary [5,4,3,2,1] — Slope is always falling → converges to index 0; only valid if treated as a monotone-unimodal edge.Explore edge cases

Edge cases handled

peak at the boundary [5,4,3,2,1]Slope is always falling → converges to index 0; only valid if treated as a monotone-unimodal edge.
two-element array [2, 5]mid=0, arr[0]<arr[1] → lo=1 → peak index 1.
real function with very flat topStill converges near the max, but precision is limited; widen the iteration count if needed.

Pitfalls

Using ternary search on a non-unimodal or plateaued function — the discard rule becomes invalid.
Flipping the comparison direction (max vs min) and converging on the wrong extremum.
Looping until f(m1) == f(m2) on reals — float equality may never hold; iterate a fixed count.
Off-by-one in the two-probe integer version — prefer the f(mid) vs f(mid+1) form.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Assuming unimodality that isn't there

If the function has two peaks or a flat region, comparing two probes can point toward the wrong region, and ternary search converges to a non-global point. Verify the precondition first.

Explore the code comparison

Don't write this

# arr = [9, 7, 4, 6, 10] has two 'uphill' directions
idx = peak_index(arr)   # meaningless: not unimodal

Write this instead

# Ensure strictly-up-then-down before using ternary search;
# otherwise fall back to a linear scan.

Wrong discard direction for max vs min

For a maximum, f(m1) < f(m2) means go right. For a minimum the logic inverts. Copy-pasting the max version to find a min silently returns the wrong extremum.

Explore the code comparison

Don't write this

# finding a MIN but using the MAX comparison
if f(m1) < f(m2):
    lo = m1   # wrong for a minimum

Write this instead

# minimum: keep the side with the smaller value
if f(m1) < f(m2):
    hi = m2
else:
    lo = m1

Looping on float equality

On real intervals f(m1) == f(m2) may never become exactly true, so a while loop on equality can spin forever. Use a fixed iteration count or an epsilon width.

Explore the code comparison

Don't write this

while f(m1) != f(m2):   # may never terminate on floats
    ...

Write this instead

for _ in range(200):    # fixed iterations -> well within precision
    ...

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Binary search on the derivative's sign over a unimodal range

Code pattern to memorize

MAX of unimodal:
while hi - lo > 2:
    m1 = lo + (hi - lo) / 3
    m2 = hi - (hi - lo) / 3
    if f(m1) < f(m2): lo = m1 + 1   # peak is right of m1
    else: hi = m2 - 1               # peak is left of m2
answer = best f over [lo..hi]

DISCRETE shortcut: compare f(mid) vs f(mid+1) to decide which half holds the peak.

Rules to remember

1The function must be strictly unimodal — one peak (or one valley), no flat plateaus. Ternary search breaks on flats because f(m1) == f(m2) gives no direction.
2You're searching on the shape (slope), not the value — there's no target to match, you're locating the turning point.
3For a maximum: f(m1) < f(m2) ⇒ still climbing, discard the left third; else discard the right third. Flip both comparisons for a minimum.
4On integers, stop when the window is tiny (≤ 2–3 elements) and scan the rest, or use the f(mid) vs f(mid+1) slope test to avoid rounding traps.
5On reals, iterate a fixed number of times (e.g. ~100/200) or until the interval is within epsilon — don't loop on exact equality.

Use this pattern when

Optimize a single-peaked / single-valley function (maximize or minimize)
Peak in a bitonic / mountain array
Geometry: minimize distance to a point along a parametrized path
Any cost function known to be convex/concave over the search range

Choose another pattern when

Function is monotonic (only increasing or only decreasing) → plain binary search, not ternary
Function has multiple peaks / not unimodal → ternary search gives a wrong local answer
Plateaus exist (equal values over a stretch) → the comparison can't pick a side; rethink the model
You're matching a target value, not finding an extremum → ordinary binary search

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Peak Index in a Mountain Array
Coming soon
Exactly the discrete slope binary search — compare arr[mid] with arr[mid+1].
Find Minimum in Rotated Sorted Array
A different shape, but the same 'compare to a neighbor/endpoint to pick a half' idea.
Minimize a Convex Cost over an Integer Range
Coming soon
Ternary search on the integer index, then check the final tiny window exhaustively.
Geometric Min-Distance Along a Path
Coming soon
Distance to a point along a straight segment is unimodal — ternary search the parameter t.

←

Floor and Ceil in a Sorted Array

Continue · Next problem

Pairs