Why it works
- Past the ends there is −∞, so walking uphill always reaches a peak: the slope cannot rise forever and has to turn down, at the latest past the end.
- If nums[mid] < nums[mid + 1], the slope rises to the right, and a peak is after mid. If not, it falls to the right: either mid is a peak or going left from it is uphill, so a peak is at mid or before it.
- Any peak is a valid answer, so dropping a half that also has one is fine. Here the first step drops the half with 8 and climbs to 9.
Complexity
Time O(log n): every step halves the range. Memory O(1): three indices.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗