Find Peak Element

题目

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

Given an input array wherenum[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine thatnum[-1] = num[n] = -∞.

For example, in array[1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

思路分析

这道题是让找到local的peak element，也就是说这个peak element不一定是global的peak element，但它一定是局部的一个peak element。怎么找到这个local的peak element呢？这道题可以使用binary search算法来实现，具体为：

• 当nums[i] > nums[i-1] and nums[i] > nums[i+1]时， nums[i] is a local peak element
• 当nums[i] > nums[i-1] and nums[i] < nums[i+1]时， local peak element is in the range of [0, i-1]
• 当nums[i] < nums[i-1] and nums[i] > nums[i+1]时， local peak element is in the range of [i+1, len]
• 当nums[i] < nums[i-1] and nums[i] < nums[i+1时],，local peak element can be either in the range of [0, i-1] or [i+1, len]

通过上面的分析可以看出，用binary search 是可以来实现的，但是关键点有两个：

• 当i=0时，i-1=-1，这个时候该怎么取值，怎么对比？单独把index 0 拿出来
• i+1可能会边界溢出，在left pointer=right pointer的时候 left pointer + 1会溢出，怎么办？循环的时候去掉这种情况就可以了

class Solution(object):
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 1 or nums[0] > nums[1]: return 0  <<< Seperate the index 0
        left = 1
        right = len(nums) - 1
        while left < right:     <<<< use left < right, instead of left<=right to avoid left+1 = len(nums)
            mid = left + (right-left)/2
            if nums[mid] > nums[mid-1] and nums[mid] > nums[mid+1]: 
                return mid
            elif nums[mid] > nums[mid-1] and nums[mid] < nums[mid+1]: 
                left = mid + 1
            else: 
                right = mid - 1
        return left