[LeetCode] 162. Find Peak Element_Medium tag: Binary Search

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

Given an input array?nums,where?nums[i] ≠ nums[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 that?nums[-1] = nums[n] = -∞.

Example 1:

Input: nums = 
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.[1,2,3,1]

Example 2:

Input: nums = 1,1,5,6,4]
Output: 1 or 5 
Explanation: Your function can return either index number 1 where the peak element is 2,?            or index number 5 where the peak element is 6.
[

Note:

Your solution should be in logarithmic complexity.

思路就是要么在上升(l = mid),要么在下降(r = mid),要么在谷底或者顶点(l = mid or r = mid) 都可以.最后判断A[l] < A[r],return r else l

Code

class Solution:
    def findPeakElement(self,nums):
        l,r = 0,len(nums)-1  # 可以是0 or len(nums) -1
        while l + 1 < r:
            mid = l + (r-l)//2
            if nums[mid] < nums[mid - 1]:
                r = mid
            elif nums[mid] <  nums[mid + 1]:
                l = mid
            else:
                l = mid  # or r = mid 
        if nums[l] < nums[r]:
            return r
        return l