Binary Search Python Solution with detailed explanation


  • 1
    L
        as said in the question, nums[-1] and nums[n] can be float("inf"),
        and we should try to use binary search to reach O(logN)
        the problem becomes how can we divide the problem when we use binary search,
        the key is to make the sub problem in half size and make sure we can get one peek in sub problem
        we found that in range(i....j)
            if nums[i-1]<nums[i] and nums[j]>nums[j], we can make sure there is a peek in (i...j)
            because if no peek, (i-1...j+1) should be ascending or descending, which is impossible
    
        based on above , when we get mid,
        if nums[mid]<nums[mid+1],
            sub problem becomes (mid+1....r)
        else
            sub problem becomes (l....mid)
    
    class Solution(object):
        def findPeakElement(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            l, r = 0, len(nums) - 1
            while l <= r:
                if l == r:
                    return l
                else:
                    mid = (l + r) / 2
                    if nums[mid] < nums[mid + 1]:
                        l = mid + 1
                    else:
                        r = mid
    
    

  • 0
    A

    Just find you don't need to have an if condition l==r if you drop the '=' in while:

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

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.