Find Peak Element

这道题没有逃脱二分的变体题的一般思路，即其实这些题都是在基础二分法的基础上找到一个另外的规律来代替原先二分缩小范围的方法来进行搜索并缩小范围，而这道题的话，就在于对mid的临近两点进行判断，如果mid比左右两边都小，则我们可以用任意半边，因为这两边都有peak element的解，如果是斜坡型，则往上坡的那半边找，如果比两边都大则mid就是peak element 了，此题需要考虑一些边界情况如n等于1，此时这个元素就是解，如果n等于2，则我们找相对大的那个值，因为这道题比较适合使用九章的二分模板来避免越界情况，另外注意此题保证必定有解，如果无解我们还需要对一些判断进行更改，下面是代码

class Solution(object):
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        if n == 1:
            return 0

        start, end = 0, n - 1
        while start + 1 < end:
            mid = start + (end - start) / 2
            if nums[mid - 1] < nums[mid] < nums[mid + 1]:
                start = mid
            elif nums[mid - 1] > nums[mid] > nums[mid + 1]:
                end = mid
            elif nums[mid] > nums[mid - 1] and nums[mid] > nums[mid + 1]:
                return mid
            else:
                end = mid

        return start if nums[start] > nums[end] else end

这里拿LeetCode的解对比一下，LeetCode的解是保证在有解得情况下使用的

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

二刷的代码，感觉不错了

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

        return start if nums[start] > nums[end] else end