Find Peak Element

How it works

We can simplify the binary search by using l < r as the loop condition instead of l <= r. This eliminates extra boundary checks. By always comparing mid with mid + 1, we ensure we move toward a peak. When l == r, we have found the peak without needing additional checks.

Steps

1. Initialize l = 0 and r = n - 1.
2. While l < r:
   • Compute m = (l + r) / 2.
   • If nums[m] > nums[m + 1], the peak is at m or to the left, so set r = m.
   • Otherwise, the peak is to the right, so set l = m + 1.
3. When the loop exits, l points to a peak. Return l.

Complexity

• Time complexity: O(log n)
• Space complexity: O(1)

Things to watch for

Incorrect Boundary Handling

When accessing nums[m-1] or nums[m+1], you must check that m > 0 or m < n-1 respectively to avoid array index out of bounds errors. Elements outside the array are conceptually negative infinity, so boundary elements can be peaks if they are greater than their single neighbor.

Using Wrong Loop Condition

Using l <= r versus l < r changes the termination logic significantly. With l < r, when the loop exits, l and r converge to the peak index. With l <= r, you need explicit return statements inside the loop. Mixing these approaches incorrectly leads to infinite loops or missed peaks.

Misunderstanding the Peak Guarantee

The problem guarantees that a peak always exists because adjacent elements are distinct and boundaries are treated as negative infinity. Some solutions incorrectly return -1 or handle the "no peak found" case, which is unnecessary. Understanding why a peak must exist (the array cannot be strictly increasing forever due to the right boundary) helps avoid overcomplicating the solution.

from typing import List

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        l, r = 0, len(nums) - 1

        while l < r:
            m = (l + r) >> 1
            if nums[m] > nums[m + 1]:
                r = m
            else:
                l = m + 1

        return l

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;

        while (l < r) {
            int m = (l + r) >> 1;
            if (nums[m] > nums[m + 1]) {
                r = m;
            } else {
                l = m + 1;
            }
        }

        return l;
    }
};