Find Peak Element: Binary Search Without a Fully Sorted Array
Find Peak Element is a very good example of an algorithm problem that looks easier than it first appears and then turns out to be easier in a completely different way. Many first solutions use a linear scan, which is fine for correctness. The more interesting part is understanding why binary search still works even though the array isn't sorted in the usual sense.
That's the real lesson of the problem. Binary search isn't only for exact matches in sorted arrays. It's also for situations where a comparison lets us discard half of the search space with confidence. Seen that way, the solution becomes much more intuitive.
What the Problem is Really Asking
In the original challenge, the array is non‑empty, contains finite integers, and adjacent values are unequal. A peak must be strictly greater than its neighbours; values beyond either end are treated as negative infinity. We need any valid peak, rather than the maximum value in the whole array. These assumptions are what make the directional argument work.
Why Binary Search Works
At any midpoint, we can compare the current value with the value to its right. If the right neighbour is larger, there must be a peak somewhere on the right side. If the current value is larger, there must be a peak on the left side, including the midpoint itself. That lets us eliminate half the array at each step.
This is a useful misconception to clear up: the array doesn't need to be globally sorted for binary search to be valid. It only needs a comparison rule that preserves a trustworthy direction.
Why a Peak Always Exists in the Chosen Half
This is the part that makes the method feel safe rather than magical. If values[middle] < values[middle + 1], the slope is rising to the right. That rise must eventually end at a peak, whether because the array turns downward later or because it reaches the boundary.
If the midpoint is not smaller than its right neighbour, it must be larger under the unequal‑adjacent‑values condition. A peak therefore exists on the left side, including the midpoint. An input such as [1, 1] is outside this contract: neither value is a strict peak.
A Practical TypeScript Solution
export const findPeakElement = (values: number[]): number => {
if (values.length === 0) {
throw new RangeError('A non-empty array is required');
}
// Caller supplies finite integers with unequal adjacent values.
let left = 0;
let right = values.length - 1;
while (left < right) {
const middle = Math.floor((left + right) / 2);
if (values[middle] < values[middle + 1]) {
left = middle + 1;
} else {
right = middle;
}
}
return left;
};The loop narrows the search window until left and right meet at a peak index. The helper rejects an empty array, but relies on the caller to supply the challenge's finite‑integer and unequal‑adjacent‑value conditions. Checking the entire input for those conditions would add a linear pass.
Why the Linear Solution is Still Worth Knowing
A linear scan is easier to derive on the spot and perfectly acceptable if the goal is simply correctness without the logarithmic constraint. In interviews or deliberate practice, though, the binary‑search version is where the deeper understanding sits. It trains us to ask what structure the problem is quietly giving us, even when the input doesn't look sorted at first glance.
Complexity and Edge Cases
The binary‑search solution runs in O(log n) time and O(1) extra space. That is the practical reason the problem is usually framed this way.
It is also worth testing a few edge shapes deliberately:
- a single‑element array should return index
0 - a strictly increasing array peaks at the right edge
- a strictly decreasing array peaks at the left edge
- arrays with several peaks can return any valid one
Why the Approach Holds up
This function is easy to test because boundary cases are clear: single‑item arrays, rising sequences, falling sequences, and arrays with several possible peaks. Maintainability comes from documenting the directional rule, because that is the part future readers are least likely to infer immediately. Scalability is strong because the algorithm stays logarithmic even as the input grows.
If we want the original challenge wording and the underlying details behind the solution, these references are the useful ones to keep nearby:
What the Interviewer Usually Wants
This problem is less about memorising a special‑case binary search and more about trusting the local signal. Once we see that a rising slope guarantees a peak somewhere to the right, the logic becomes much calmer. That is often the real test: can we reason from the structure of the problem instead of reaching for a pattern mechanically?
Once we see that, the logarithmic solution feels earned rather than memorised, which is exactly the difference a good interviewer is usually trying to hear.
It is a small leap, but a very useful one.
Wrapping Up
Find Peak Element is valuable because it teaches a broader lesson about binary search. The technique becomes much more flexible once we recognise that safe elimination matters more than exact matching.
Key Takeaways
- We only need one valid peak, not the global maximum.
- Local slope comparisons are enough to eliminate half the search space each step.
- Binary search applies whenever the comparison rule gives us a trustworthy direction.
Find Peak Element is satisfying because it stretches the usual definition of binary search without breaking it. Once the direction rule clicks, the problem becomes a lot less mysterious and a lot more memorable.