162. Find Peak Element

# Medium

二分法中心思想：

要么留下可能的一半，要么去掉不可能的一半

Solution 1:

1. find first ascending position from begining as left, and first ascending position from the end as right

2. compute mid, keep the possible part according to left and right slope of mid（3 cases: mid is lowest peak then both of left and right are possible, mid is higheset peak then return, mid's left or right part is possible ）

3. edge cases: 1 element, ascending list, descending list

极端例子很容易忽略掉

Solution 2:

Q1: why this question can use binary search?

A1: Because the question precondition is nums[0] and nums[n] are assumed as infinite, then both of the starting and ending are regarded as an ascending line, there must be a peak point. If nums[mid] > nums[mid+1], then we know there must be a peak in [left, mid] (mid still may be a peak element), otherwise the other part of the line must have a peak point. In another way, binary search means you have a condition can discard half of the searching range. This case satisfies the condition, so we can use BS.

Q2: why only compare nums[mid] and nums[mid+1] instead of nums[mid-1]?

A2: Because mid always is the element nearby left not right, let's imagine if the array only has two elements [1, 2], then mid = 0, mid-1 = -1 which is out of index, but (mid+1) won't cause the problem at all.

Q3: why left = mid +1, but right = mid?

A3: Imaging a hill, if nums[mid] < nums[mid+1], then it's a uphill, we already know nums[mid+1] is bigger, so nums[mid+1] is possible to be the peak, so left = mid + 1. If nums[mid] > nums[mid+1], then this is a downhill, nums[mid] is bigger, so it is possible to be the peak in [left, mid], it's why right = mid.

Q4: why the loop condition is "left < right" instead of "left <= right"?

A4: Because "left = mid+1 or right = mid", this is different from the original BS code “left = mid + 1 or right = mid - 1", so the stop situation is very different. In original BS code, stop situation is left = right + 1, so loop condition is left <= right is reasonable. But in this case, after using some test cases to try, we can see the stop situation is always left == right, so the loop condition is left < right.

Q5: why return left but not others?

A5: In Q4, I explained the stop condition is left == right, so actually both of return left and right are correct (I ran this in LeetCode, pass). Eventually the BS will find the peak point, we only have one element left in array, so the only one element should be the peal point, then return.

Java iteration

// Some code
class Solution {
    public int findPeakElement(int[] nums) {
        // edge case
        if(nums.length == 1)
            return 0;

        // regular case
        int left = 0, right = nums.length - 1;
        while(left < right) {
            int mid = left + (right - left)/2;
            if(nums[mid] > nums[mid + 1])
                right = mid;
            else
                left = mid + 1;
        }
        
        return left;
    }
}jav

Java recursion

// Some code
class Solution {
    public int findPeakElement(int[] nums) {
        return searchPeak(nums, 0, nums.length - 1);
    }
    
    public int searchPeak(int[] nums, int left, int right) {
        // stop condition
        if(left == right)
            return left;
        if(left + 1 == right)
            return nums[left] > nums[right] ? left : right;
        
        // regular case
        int mid = left + (right - left)/2;
        if(nums[mid] > nums[mid + 1])
            return searchPeak(nums, left, mid);
        return searchPeak(nums, mid + 1, right);
    }
}

Python iteration

// Python3
class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        left = 0
        right = len(nums) - 1
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] < nums[mid + 1]:
                left = mid + 1
            else:
                right = mid
                
        return left