A peak element is an element that is strictly greater than its neighbors. Given a 0-indexed integer array nums, find a peak element and return its index. If the array contains multiple peaks, return the index of any of the peaks. You may imagine that nums[-1] = nums[n] = -∞. You must write an algorithm that runs in O(log n) time.
nums = [1,2,3,1]2nums = [1,2,1,3,5,6,4]5 (or 1)lo = 0, hi = n−1lo < hi: compute mid = lo + (hi−lo)/2nums[mid] < nums[mid+1]: slope goes UP → peak is RIGHT → lo = mid+1hi = midlo == hi → that index is the peak → return loBecause the array has no equal adjacent elements and the virtual boundaries are −∞, a peak must exist. At any mid, if nums[mid] < nums[mid+1] the right side is going up — there's definitely a peak somewhere to the right (at minimum the next element is higher, and since the array must come back down, a local max exists). We safely eliminate the left half. The symmetric argument applies for the down slope.
Scanning for an element bigger than both neighbours is O(n). The array is not sorted, but the slope still tells us where to go.
Compare the middle with its right neighbour. If the right neighbour is bigger, the slope goes up, so a peak must exist on the right. Otherwise, the middle or something on its left is a peak.
Walk uphill, and you must reach a peak. Binary search works on any direction you can decide locally.
Run the animation above on your own input, or watch the 1:17 video explanation of Find Peak Element with a dry run and Java code.