162. Find Peak Element

Time: O(log n)

Space: O(1)

Intuition

A peak exists on the side where the slope is ascending. If nums[mid] < nums[mid+1], the peak is to the right (ascending right); otherwise it's to the left or at mid. Binary search narrows to one element - that is a peak.

Algorithm

1lo=0, hi=n-1.
2While lo < hi: mid = lo + (hi-lo)/2.
3If nums[mid] < nums[mid+1]: lo = mid+1 (peak is right).
4Else: hi = mid (peak is left or at mid).
5Return lo.

Example Walkthrough

Input: nums = [1,2,3,1]

1.lo=0,hi=3. mid=1: nums[1]=2 < nums[2]=3 -> lo=2.
2.lo=2,hi=3. mid=2: nums[2]=3 > nums[3]=1 -> hi=2.
3.lo=hi=2. Return 2.

Output: 2

Common Pitfalls

•Use hi=mid (not mid-1) to include mid as a candidate - it might itself be the peak.

162.cs

// Approach: Binary search exploiting the virtual boundary rule: nums[-1] = nums[n] = -infinity.
// At index mid, compare nums[mid] with nums[mid+1].
// If nums[mid] < nums[mid+1], the right half must contain a peak (it is rising at mid).
// If nums[mid] > nums[mid+1], the left half (including mid) must contain a peak.
// At convergence lo == hi, and that index is a valid peak element.
// Unlike classical binary search, the array does not need to be globally sorted.
// Time: O(log n) Space: O(1)

public class Solution
{
    public int FindPeakElement(int[] nums)
    {
        int n = nums.Length;
        if (n == 1)
            return 0;

        if (nums[0] > nums[1])
            return 0;

        if (nums[n - 1] > nums[n - 2])
            return n - 1;
        int l = 1, r = n - 2, mid;
        while (l <= r)
        {
            mid = (l + r) / 2;
            if (nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1])
                return mid;
            else if (nums[mid] > nums[mid - 1] && nums[mid] < nums[mid + 1])
                l = mid + 1;
            else
                r = mid - 1;
        }

        return -1;
    }
}

Was this solution helpful?