Peaks and 2D

What is this?

Here binary search escapes the sorted list entirely. A "peak" is just a value bigger than its neighbours — think of hiking and always stepping toward the higher of the two sides; you're guaranteed to reach a summit, and you get there in a handful of steps instead of walking the whole ridge. The "2D" half plays a different game: a grid whose rows are sorted and stacked in order is secretly one long sorted line in disguise, so you can read row and column off a single position and search it like any ordinary array.

💡 Fun fact: The "always walk uphill" idea behind peak-finding is the oldest optimization method there is — hill climbing. It powers everything from autofocus on your phone camera hunting the sharpest image to early machine-learning models tuning their own weights.

🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

Core idea: Binary search does not require a fully sorted array — it only requires that the middle element tell you which half to keep. When data has a local slope you can climb toward higher ground, and when a 2D grid is sorted row by row you can pretend it is one long sorted line. Both turn an O(n) or O(mn) scan into O(log n).

The pattern

The unifying move is the same as classic binary search: probe the middle, decide which half cannot hold the answer, and discard it. What changes is the signal you read at mid.

For peaks, there is no global order, but there is direction. Compare mid to its neighbour: the slope is rising on one side, falling on the other, and a peak is guaranteed to exist in the rising direction. So you climb toward the higher neighbour — that half always contains a peak, and you keep halving until the pointers meet on one.

For grids, the trick is to flatten. A matrix whose rows are sorted and whose every row starts after the previous one ends behaves exactly like a single sorted array of length m × n. Map a virtual index k to (k / cols, k % cols) and run an ordinary binary search over 0 … m·n − 1. When only columns or only rows are sorted, binary-search along the sorted dimension and scan the other.

The problems

Peak Index in a Mountain Array — the array strictly rises then strictly falls. Compare mid to mid + 1: if it is still rising, the peak is to the right, otherwise it is at mid or to its left. Climb toward the higher neighbour until the window closes on the summit.

Find a Peak Element II — a 2D peak is a cell greater than all four neighbours. Binary search on columns: pick the middle column, find its maximum row, and move toward whichever side has a larger neighbour — that side is guaranteed to contain a 2D peak. Each step is O(m) to scan a column, giving O(m log n).

Search a 2D Matrix — rows sorted and each row's first value exceeds the prior row's last. Treat the grid as one sorted array of m·n elements; convert the midpoint index to (row, col) and binary-search normally for O(log(m·n)).

Key takeaways

• Sortedness is optional; a decisive midpoint is not. A local slope is enough to binary-search a peak.
• Climb toward the higher neighbour. A peak always lies on the rising side, so that half is safe to keep.
• Flatten a sorted grid into one virtual array. Index math (k / cols, k % cols) turns 2D search into 1D.
• Search the sorted dimension, scan the other. For peak-in-a-grid, binary-search columns and scan each column's max.
• Why this chapter matters: it breaks the myth that binary search needs full order, opening it up to slopes, grids, and any data with a reliable directional signal.