0162.md

162. Find Peak Element

Level:

Topic:

Question

Given an 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.

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Intuition

It's to return any of the peaks, so the goal is find the rightmost peak.

1,2,1,3,5,6,4
  ^       ^

As we can see, both 2 and 6 are the peak value. In order to know the it's a peak, compare with its left, if it's greater, it might be the peak, so we have to keep searching to the right until no more value is greater than the left.

Code

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

public int findPeakElement(int[] nums) {
    int low = 0, high = nums.length-1;

    while (low < high) {
        int mid = low + (high-low)/2;
        if (nums[mid] < nums[mid+1])
            low = mid+1;
        else
            high = mid;
    }

    return low;
}