Peak Element

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 to any of the peaks. You may imagine that nums[-1] = -∞ and nums[n] = -∞. Input: nums = [1, 2, 1, 3, 5, 6, 4] -> Output: 1 or 5. Constraint: You must write an algorithm that runs in $O(\log N)$ time.

We can find a peak by treating the array as a mountain range and following the upward slope. If we drop onto a random point mid and see that the next step mid + 1 is higher, we are walking uphill, meaning there must be a peak to our right. Conversely, if mid + 1 is lower, we are on a downward slope, meaning there must be a peak to our left (or mid itself is the peak). By always moving towards the higher ground, we can eliminate half the mountain at every step using Binary Search, even though the array is not globally sorted.

1. Initialize two pointers: left = 0 and right = len(nums) - 1.
2. Run a while loop as long as left < right.
3. Calculate the mid point.
4. Compare arr[mid] to its right neighbor arr[mid + 1].
5. If arr[mid] < arr[mid + 1] (ascending slope), the peak is to the right. Set left = mid + 1.
6. If arr[mid] > arr[mid + 1] (descending slope), the peak is at mid or to its left. Set right = mid.
7. When the loop terminates (left == right), the pointers will have converged on a peak. Return left.

• Using left <= right in the while loop condition. Because we are accessing arr[mid + 1], a <= condition can cause an IndexError when left and right converge on the last element.
• Setting right = mid - 1 when arr[mid] > arr[mid + 1]. If mid is the peak, subtracting 1 will skip over it. right must be set to mid to keep the potential peak inside the search space.
• Overcomplicating the logic by checking both arr[mid - 1] and arr[mid + 1]. You only need to check one direction to determine the slope!

This problem shatters the common misconception that Binary Search only works on fully sorted arrays. The true requirement for Binary Search is simply that we have a reliable way to eliminate half of the search space at each step. By leveraging local gradients (slopes), we can apply $O(\log N)$ efficiency to seemingly chaotic data.