Find Peak Element
A peak is an element strictly greater than its neighbours. Given an unsorted array where nums[i] != nums[i+1], return the index of any peak in O(log n). Treat out-of-bounds neighbours as negative infinity.
Intuition
Binary search on an unsorted array sounds impossible, and it would be if the problem asked for the peak. It asks for any peak — and that weaker requirement is what makes the halving valid. Compare the midpoint with its right neighbour. If we are on an upward slope, keep walking right and the values must eventually stop rising (the boundary acts as negative infinity), so a peak is guaranteed somewhere to the right. If we are on a downward slope, the same argument guarantees a peak to the left. Either way, half the array can be discarded while preserving the guarantee.
Binary search without a sorted array. Comparing nums[mid] to its right neighbour tells you which side must contain a peak: if the slope rises, a peak exists to the right; if it falls, one exists at or left of mid. The out-of-bounds -∞ convention guarantees a peak always exists.
Approach
Understand why the sentinel boundaries matter
The problem defines nums[-1] and nums[n] as negative infinity. That is not a technicality — it is what makes a peak always exist. Walk uphill from anywhere and you cannot walk forever, because the array ends and the sentinel is lower than any real element. So every array has at least one peak, and every ascending run terminates in one.
Turn the slope into a halving rule
At index mid, compare nums[mid] with nums[mid+1]. If nums[mid] < nums[mid+1] we are ascending: the segment from mid+1 rightward starts by going up and ends at a sentinel, so by the argument above it must contain a peak. Discard mid and everything left of it. If nums[mid] > nums[mid+1] we are descending: the segment from 0 to mid ends by going down into mid, so it contains a peak — and mid itself may be it, so keep mid and discard everything to its right.
Shrink until one element remains
Loop while lo < hi, never lo <= hi — the invariant is that the window always contains a peak, so the moment it narrows to a single index that index is a peak. Note the asymmetry in the updates: lo = mid + 1 on the ascending branch (mid is excluded, since we know something to its right is bigger) but hi = mid on the descending branch (mid is retained, since it may be the peak). Getting that asymmetry wrong is the usual bug here.
Solution & live demo
Common pitfalls
Setting hi to mid - 1 on a descent
else:
hi = mid - 1else:
hi = midWhen nums[mid] > nums[mid + 1], mid itself may be the peak. Excluding it can discard the only answer in that half and the search converges on a non-peak.
Comparing with both neighbours
if nums[mid-1] < nums[mid] > nums[mid+1]: return mid
if nums[mid] < nums[mid + 1]:
Needs bounds guards on both sides and doesn't help the search decide where to go when the test fails. The single right-neighbour comparison always determines a half that must contain a peak.
Scanning linearly
for i in range(n):
if is_peak(i): return iwhile lo < hi:
Correct but O(n), and the problem asks for O(log n). The slope argument makes half the array discardable at every step even though nothing is sorted.
Edge cases
The loop never runs and index 0 is returned — correct, since both neighbours are negative infinity.
Every comparison takes the ascending branch, driving lo to the last index, which is the peak.
Every comparison takes the descending branch, driving hi to 0, which is the peak.
Any one is acceptable. The search commits to whichever half it enters and returns the peak it finds there.