/ Data Structure and Algorithms  

Leetcode 162. Find Peak Element

Question



Give an array, find any peak. The peak is larger than its left and right neighbors.

Similar Questions

Solution 1 - Linear scan

Because nums[-1] is regarded as negative infinity, so start from the 0-th element the array must be an upward trend. Since we are looking for the peak, when it first falls, the value before the decline is what we are looking for.

If it rises to the last value, and because nums[n] is regarded as negative infinity, the last value can be regarded as a peak.

1
2
3
4
5
6
7
8
9
10
11
public int findPeakElement(int[] nums) {
    for (int i = 0; i < nums.length - 1; i++) {
        // first decline
        if (nums[i] > nums[i + 1]) {
            return i;
        }
    }

    // always increasing
    return nums.length - 1;
}

We generally use binary search on ordered arrays, so why can we use it for this problem?

In any case, the reason why we can use binary search is because we can directly discard half of the elements according to a certain condition, thereby reducing the time complexity to logarithmic level.

As for this question, because the question tells us that we can return any peak in the array. So as long as there is at least one peak in one half, the other half can be discarded.

We only need to compare nums[mid] and nums[mid + 1].

Consider the first search, start = 0, end = nums.length - 1.

If nums[mid] < nums[mid + 1], the left part is in the ascending phase, because nums[n] is regarded as negative infinity, so it will eventually fall, so there will be at least one peak between mid + 1 and end, we can discard the left half.

If nums[mid] > nums[mid + 1], the right part is in the descending phase, because nums[0] is regarded as negative infinity, it must initially be the ascending phase, so there will be at least one peak between start and mid, we can discard the right half.

Through the cutting above, we ensure that the subsequent left part must be rising, and the right part must be falling, so the second and third search is the same as the above.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int findPeakElement(int[] nums) {
    // binary search
    int start = 0;
    int end = nums.length - 1;

    while (start < end) {
        int mid = (start + end) / 2;

        // peak in left part
        if (nums[mid] > nums[mid + 1]) {
            end = mid;
        // peak in right part
        } else {
            start = mid + 1;
        }
    }

    return start;
}