[Leetcode][python]寻找峰值

题目大意

https://leetcode-cn.com/problems/find-peak-element/description/

峰值元素是指其值大于左右相邻值的元素。

给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。

数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞。

解题思路

二分查找变种

代码

方法1：顺序遍历。

本题的一个重要特点是，从第一个元素开始，若其大于相邻的后续元素，则第一个元素就是一个局部最大值，返回即可。若其小于相邻的后续元素，则第二个元素大于第一个元素。如此，一一遍历数组，第一次出现，第i个元素若大于其相邻后续元素，则该元素就是一个局部最大值

方法2：二分查找

思路：如果中间元素大于其相邻后续元素，则中间元素左侧(包含该中间元素）必包含一个局部最大值。如果中间元素小于其相邻后续元素，则中间元素右侧必包含一个局部最大值。

class Solution(object):
    def findPeakElement(self, nums):
        """ :type nums: List[int] :rtype: int """
        left = 0
        right = len(nums)-1
        while left <= right:
            print left, right
            if left == right:
                return left
            mid = left + (right -left) / 2 
            # 如果中间小于右边，那么一定在右边
            if nums[mid] < nums[mid+1]:
                left = mid + 1
            # 左边不小于右边，那么直接把右边弄到中间
            else:
                # right不可以是mid-1，万一正好是mid，就跳过了，因为并没有比对mid的值
                right = mid

总结