A peak is an element strictly bigger than its neighbours. Return the index of any peak in O of log n time, treating the outside as minus infinity.
DSA Animator › DSA Revision › Binary Search › Find Peak Element
Remember: walk uphill, and you must reach a peak. Binary search works on any direction you can decide locally. The video solves Find Peak Element (LeetCode 162, Medium) with the Binary Search on Slope pattern from the Binary Search topic, and you can replay every step in the interactive Find Peak Element animation.
A peak is an element strictly bigger than its neighbours. Return the index of any peak in O of log n time, treating the outside as minus infinity.
For 1, 2, 1, 3, 5, 6, 4, index 1 holding 2 is a peak, and so is index 5 holding 6.
Scanning for an element bigger than both neighbours is O of 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.
Low 0, high 6, so mid 3 holds 3, and the right neighbour 5 is bigger, so go right. Mid 5 holds 6, and the right neighbour 4 is smaller, so keep mid, and high becomes 5. Mid 4 holds 5, and 6 on its right is bigger, so low becomes 5. Low equals high, so index 5 is a peak.
In code, loop while low is less than high. If the middle value is smaller than the next one, move low to mid plus 1. Otherwise move high to mid, and return low, so it's O of log n time.
Remember: walk uphill, and you must reach a peak. Binary search works on any direction you can decide locally.