162. Find Peak Element

1. Find Peak Element

Question

A peak element is an element that is strictly greater than its neighbors.

Given a 0-indexed 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.

You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.

You must write an algorithm that runs in O(log n) time.

Example 1:

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

Example 2:

Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

Algorithm

This question is similar to question 153&154. Here we are asked to find the peak in O(log(N)). The difference is here the array is not sorted and we have multiple peaks, and we are asked to find peak(but this is not important).

The code is easy, you look for the element that is large than its neighbor, and you know you are going to search the left side.

The lesson is that by using binary search, you are not always compare the left, mid, right, target. Sometimes you have no additional target, you're asked to find an element just in the array who has some attribute(max, min, peak...); in current condition, the right is normally equals to the nums.length - 1, we want the final index be not out of bounds. And if talking about the comparison, if you are asking to find peak, in an unsorted array, you'd better compare the neighbor rather than left/right with mid. The reason is obvious, peak is larger than its neighbors, and it's not sorted, meaningless to compare the mid with left and right bound element value.

Code

class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= nums[mid+1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

Code2(updates)

class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if ((mid == 0 || nums[mid] > nums[mid - 1]) && (mid == nums.length - 1 || nums[mid] > nums[mid + 1])) {
                return mid;
            } else if (nums[mid] > nums[mid - 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left == 0 ? left : right - 1;
    }
}