Intermediate · Module 9 · Lesson 4
Peak & mountain search
Use slope direction as the monotonic clue.
15–25 min readLesson 50 of 123
Lesson 50 of 123
1d streakTheory lesson · Step-by-step
Understand Peak & mountain search
Use slope direction as the monotonic clue.
Worked approach
Trace the reasoning step by step
- 1Compare values[mid] with values[mid + 1].
- 2If rising, keep the right side including its peak.
- 3If falling, keep mid and the left side.
- 4Stop when both boundaries meet.
Concrete example
Find the peak in [1,3,5,4,2].
- 1At middle 5, the next value is smaller.
- 2A peak exists at middle or to its left.
Peak value 5 is at index 2.
What must remain true (Loop Invariant)
The local slope around mid points toward a side containing a peak.
Cost Model
Complexity & Trade-offs
OperationTimeSpaceWhy
Search
O(log n)
O(1)
Each valid decision removes half of a monotonic search space.When to use it
- Exact lookup, first/last occurrence, rotated order, and answer-space optimization.
- Any monotonic yes/no feasibility boundary.
- Implicit ordered spaces where values need not be materialized.
Common mistakes
- Mixing inclusive and half-open interval updates.
- Using binary search without proving monotonicity.
- Returning the last middle value instead of the stored boundary.
Practice prompts
- Reproduce the worked Peak & mountain search example without looking at the trace.
- Change one input condition and explain whether the Peak & mountain search invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check
Can you derive it instead of memorizing it?
State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.