Find Peak Element

Problem in plain words

You get an array where no two neighbours are equal. A peak is any position whose value is larger than both of its neighbours, and you should pretend there is negative infinity just beyond each end of the array. Return the index of any one peak, and do it in logarithmic time, so a simple left-to-right scan is not what the problem wants.

For example, in [1, 6, 2, 8, 3] both index 1 (value 6) and index 3 (value 8) are peaks, and returning either is accepted.

Intuition

Look at any middle index mid and its right neighbour. If nums[mid] < nums[mid + 1], the array is climbing at that point. Keep walking right: either it keeps climbing until the last element (which is a peak because the outside is negative infinity), or it turns downward somewhere, and the turning point is a peak. Either way, a peak is guaranteed to exist to the right of `mid`. The mirror argument says that if nums[mid] > nums[mid + 1], a peak exists at mid or to its left.

So the array does not need to be sorted for binary search to work. We are not searching for a value; we are searching for a place where the slope changes, and each comparison safely throws away half the range. This is the same shrinking-window idea covered in the binary search lesson.

Approach

1. Set lo = 0 and hi = n - 1. The answer always stays inside [lo, hi].
2. While lo < hi, compute mid = lo + (hi - lo) / 2. Because lo < hi, mid + 1 is always a valid index.
3. If nums[mid] < nums[mid + 1], we are on an uphill slope, so set lo = mid + 1.
4. Otherwise we are on a downhill slope (or at a peak), so set hi = mid. Do not skip mid itself, it might be the peak.
5. When lo == hi, that index is a peak. Return it.

Dry run

Input: nums = [2, 5, 7, 4, 1, 3].

Index 2 holds 7, which is bigger than 5 and 4. Note that index 5 (value 3) is also a peak; the algorithm simply found a different valid one.

Java solution

class Solution {
    public int findPeakElement(int[] nums) {
        int lo = 0, hi = nums.length - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] < nums[mid + 1]) {
                lo = mid + 1;   // climbing: a peak lies to the right
            } else {
                hi = mid;       // falling: a peak is at mid or to the left
            }
        }
        return lo;
    }
}

Python solution

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        lo, hi = 0, len(nums) - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] < nums[mid + 1]:
                lo = mid + 1   # climbing: a peak lies to the right
            else:
                hi = mid       # falling: a peak is at mid or to the left
        return lo

Complexity

Edge cases and common mistakes

• Single element: lo == hi from the start, so index 0 is returned immediately, which is correct because both outside neighbours are negative infinity.
• Strictly increasing array: the search keeps moving right and returns the last index.
• Strictly decreasing array: the search keeps moving left and returns index 0.
• Comparing with `mid - 1`: mixing left and right comparisons makes the bounds easy to break. Comparing only with mid + 1 under lo < hi never goes out of range.
• Writing `hi = mid - 1`: this can skip the actual peak when mid is the peak.