162. Find Peak Element

"""
Find Peak Element
这道题要求找出任意峰值，需要考虑三种case：
case 1：[1,2,3,4,5] 在这个单调递增的array中最后一个值是峰值。
case 2: [5,4,3,2,1] 在这个单调递减的array中第一个值是峰值。
case 3: [1,2,3,4,2] 在这种无序的array中index=3是峰值。
"""
# 方法一：线性时间复杂度，如果在array中下一位的值比当前位的值小，那么我们就说当前位是一个峰值。
class Solution(object):
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        for i in range(0, len(nums)-1):
            if nums[i] > nums[i+1]:
                return i
        return len(nums) - 1

# 方法二： 对数时间复杂度，
class Solution(object):
    def binarySearch(self, nums, l, r):
        if l == r:
            return l
        mid = (l + r) // 2
        if nums[mid] > nums[mid+1]:
            return self.binarySearch(nums, l, mid)
        return self.binarySearch(nums, mid+1, r)

    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return self.binarySearch(nums, 0, len(nums)-1)

class Solution(object):
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        l = 0
        r = len(nums)-1

        while l < r:

            mid = (l + r) // 2

            if nums[mid] > nums[mid+1]:
                r = mid
            else:
                l = mid + 1

        return l