Peak Finding
Peak finding is binary search on data that rises and then falls: compare the middle with its neighbour to learn which slope you are on. O(log n).
Peak finding locates the highest point of data that rises and then falls by looking at the middle item and its neighbour, working out which slope the middle is on, and throwing away the half that cannot hold the top. It is binary search for data that is not sorted, but is shaped like a hill.
The idea
Imagine walking on a hill in thick fog. You cannot see the summit, but you can feel the ground under your feet. If the next step forward is uphill, the summit is ahead of you. If the next step forward is downhill, you are either standing on the summit or have already passed it. One step tells you which half of the hill to ignore.
Ordinary binary search compares the middle item with a target. Peak finding has no target to compare with, so it compares the middle item with the item next to it. That single comparison gives the direction of the slope, and the slope gives the direction of the peak.
value
21 | *
17 | * *
12 | *
8 | *
4 | *
3 | *
+---------------------
0 1 2 3 4 5 6 index
└── rising ──┘ └ falling ┘An array with this shape is called a mountain array, or a bitonic array: strictly up to one peak, then strictly down.
When to use it
- The data rises then falls (or falls then rises) and you need the turning point.
- The problem asks for any local peak, an item larger than both its neighbours, in O(log n) time.
- You must search for a value in a mountain array: find the peak first, and each side of it is sorted.
- More generally: the question "is the next item bigger than this one?" is answered "yes" for a while and then "no" from some point onwards, and you want the point where it changes.
If the data is fully sorted there is nothing to find, since the peak is simply the last item. If neighbouring items can be equal, see "Plateaus break the guarantee" below.
Template 1: the peak of a mountain
function peakOfMountain(values) {
let lo = 0;
let hi = values.length - 1;
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (values[mid] < values[mid + 1]) {
lo = mid + 1; // still climbing: the peak is to the right of mid
} else {
hi = mid; // going down: the peak is mid or to its left
}
}
return lo; // lo and hi have met on the peak
}Three details work together, and each one matters:
- The loop runs while
lo < hi. It stops when the range is a single index. Nothing is "found" early; the range just shrinks until only the peak is left. values[mid + 1]is always a valid read. The middle is rounded down, so inside the loopmidis always less thanhi, andmid + 1is at mosthi.hi = mid, notmid - 1. When the slope is going down atmid,miditself may be the peak, so it stays in the range. When the slope is going up,midcannot be the peak (its right neighbour is taller), solojumps past it.
Walkthrough
peakOfMountain([3, 8, 12, 17, 21, 16, 4]):
| lo | hi | mid (value) | Next value | Slope at mid | Action |
|---|---|---|---|---|---|
| 0 | 6 | 3 (17) | 21 | Rising | lo = 4 |
| 4 | 6 | 5 (16) | 4 | Falling | hi = 5 |
| 4 | 5 | 4 (21) | 16 | Falling | hi = 4 |
| 4 | 4 | lo and hi have met | Return 4 |
Three comparisons for seven items. The tallest value, 21, is at index 4.
Why throwing half away is safe
The rule the loop keeps true is: the peak is always somewhere from lo to hi.
- If
values[mid] < values[mid + 1], thenmidis on the rising slope. On a mountain, everything to the left of a rising point is lower still, so nothing fromlotomidcan be the peak. - Otherwise
midis on the falling slope or is the peak. Everything to the right of it is lower, so nothing aftermidcan be the peak.
Either way the peak stays inside the smaller range, and the range gets smaller on every step, so the loop must end on the peak.
Template 2: the same code finds a peak in any data
Remove the promise that there is only one hill. Say the array wanders up and down, with the single rule that no two neighbours are equal, and you are asked for any index whose value is larger than both neighbours (an edge counts as a peak if it is larger than its one neighbour).
peakOfMountain already solves this, unchanged. The reasoning shifts from "where is the peak?" to "which half is certain to hold a peak?":
- If the slope rises at
mid, start atmid + 1and keep walking right. Either the values keep rising to the last item, which is then a peak, or they turn down somewhere, and the turning point is a peak. The right half must contain one. - If the slope falls at
mid, the same argument, mirrored, says the left half includingmidmust contain one.
There may be peaks in the half that is thrown away too. That does not matter: the question asks for any one of them. Find Peak Element works through this in full.
Template 3: the lowest point of a valley
Data that falls and then rises has the mirror-image shape. Flip the comparison and the same loop finds the bottom.
function bottomOfValley(values) {
let lo = 0;
let hi = values.length - 1;
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (values[mid] > values[mid + 1]) {
lo = mid + 1; // still descending: the bottom is to the right
} else {
hi = mid; // climbing again: the bottom is mid or to its left
}
}
return lo;
}bottomOfValley([9, 6, 2, 5, 7, 11]) returns 2, the index of the value 2.
Template 4: search for a value in a mountain
Once the peak is known, the mountain splits into two sorted pieces: ascending up to the peak and descending after it. Each piece can be searched with exact-match binary search. The only change on the falling side is that the comparison is reversed, because there the bigger values are on the left.
function searchSlope(values, target, lo, hi, rising) {
while (lo <= hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (values[mid] === target) return mid;
// Rising slope: small values are on the left.
// Falling slope: small values are on the right.
const goRight = rising ? values[mid] < target : values[mid] > target;
if (goRight) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return -1;
}function searchMountain(values, target) {
const peak = peakOfMountain(values);
const onTheWayUp = searchSlope(values, target, 0, peak, true);
if (onTheWayUp !== -1) return onTheWayUp;
return searchSlope(values, target, peak + 1, values.length - 1, false);
}searchMountain([3, 8, 12, 17, 21, 16, 4], 16) returns 5, and a missing value such as 10 returns -1. Three binary searches in a row are still O(log n). Find in Mountain Array builds this step by step.
Plateaus break the guarantee
Every template above relies on neighbours being different. If values[mid] equals values[mid + 1], the ground is flat, and flat ground says nothing about where the summit is:
[5, 5, 5, 5, 9, 5, 5] the peak is on the right
[5, 5, 9, 5, 5, 5, 5] the peak is on the leftBoth arrays look identical from index 3. No comparison of two neighbours can choose a side, so the worst case becomes O(n): you have to walk along the flat part. Check the problem statement for "strictly increasing" or "no two adjacent values are equal" before reaching for this pattern. Rotated arrays have the same weakness, as Find Minimum in Rotated Sorted Array II shows.
How it relates to other binary searches
| Pattern | What the middle is compared with | What that tells you |
|---|---|---|
| Binary search | The target | Which side the target is on |
| Peak finding | Its right-hand neighbour | Which slope the middle is on |
| Rotated array search | An end of the range | Which half is in order |
| Binary search on the answer | Nothing: a test is run on it | Whether the answer is higher or lower |
All four rest on the same foundation. There is a yes-or-no question that changes its answer exactly once across the range, and each step halves the range around that change. For a mountain, the question is "is the next item bigger?".
Variations
| Problem | What changes | Example |
|---|---|---|
| One guaranteed peak | Template 1 as written | Peak Index in a Mountain Array |
| Many hills, any peak will do | Same code, different proof | Find Peak Element |
| Find a value in a mountain | Peak first, then one search per slope | Find in Mountain Array |
| Falls then rises | Reverse the comparison | Template 3 above |
Complexity
- Time: O(log n). Each step halves the range. A mountain of a million items needs about 20 steps, each reading two items.
- Space: O(1). Two bounds and a midpoint.
Searching for a value (Template 4) runs three such searches one after another, which is still O(log n).
Common mistakes
- Comparing with
values[mid - 1]while rounding the middle down. When the range is two items wide,midequalslo, andmid - 1can fall off the left end of the range. Compare withmid + 1when rounding down. - Writing
hi = mid - 1. On the falling slopemidmay be the peak. Discarding it loses the answer. - Writing
lo = mid. With the middle rounded down this changes nothing on a two-item range, and the loop never ends. - Looping while
lo <= hi. Withhi = midthe range stops shrinking once it holds one item, so this also loops for ever. - Forgetting to reverse the comparison on the falling side. An ascending binary search on descending data walks away from the target and reports -1 for values that are present.
- Using it on data with flat stretches. Equal neighbours give no slope. The code still returns an index, but it may not be a peak.
Practise
- Peak Index in a Mountain Array (easy): Template 1.
- Find Peak Element (medium): any peak in data with many hills.
- Find in Mountain Array (hard): the peak, then a search on each slope.
Practice problems
| Problem | Difficulty | Time | Space | Read |
|---|---|---|---|---|
| Peak Index in a Mountain Array | easy | O(log n) | O(1) | Medium read: 7 min |
| Find Peak Element | medium | O(log n) | O(1) | Long read: 9 min |
| Find in Mountain Array | hard | O(log n) | O(1) | Long read: 10 min |