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.

这题一开始看二分法的用法并不明显，可能会不知道从哪里开始找起。我们来分析下给出的东西是否满足二分法执行的条件

1. 进行二分的数据 - 这个很明显给了

2. 进行二分的区间: 这个我们如果看题能够发现，第一个和最后一个数是肯定不能够是 peak 的，所以我们的区间就是1 到 length - 2

3. 要查找的 target - peak 的定义就是num[peak] > num[peak-1] && num[peak] > num[peak+1]，那么这个也满足了

4. 最后就是指针的移动: 这个也就是找一题的考点，我们需要分析可能的情况来看我们的指针应该如何改变

这题我们举个栗子画个图 比如说[1, 2, 1, 3, 4, 5, 7, 6], 画出来的图是长下面这样的。

            /\
          .   \
         / 
        /
       /
 /\   . 
/  \/  
________________________
1 2 1  345  7 6

题目要求找这里面的 peak，也就是这图中的 2 和 7。

那么我们用过仔细的观察，可以发现这图中，任意一个点，可能是以下4种情况

• /\自己本身就是一个 peak

• /在一个递增的坡上

  那么我们知道这个点后面肯定有一个 peak，因为题目规定最后一个值是比他前一个值肯定要小的

• \

  在一个下降的坡上，那么这个点前面肯定有一个 peak

• \/在一个谷里面, 那么这个时候两边都肯定有 peak，因为要两个 peak 才能形成一个谷。

时间 O(logn)

进行一次二分搜索

空间 O(1)

class Solution(object):
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
           # return nums.index(max(nums))
        start, end = 0, len(nums)-1
        while start+1<end:
            mid = (start+end)/2
            if nums[mid] < nums[mid+1]:
                start = mid
            else:
                end = mid
        if nums[start] > nums[start-1] and nums[start]>nums[start+1]:
            return start
        return end