Python binary search solution - O(logN) 40ms


  • -3
    G
    class Solution:
        # @param {integer[]} nums
        # @return {integer}
        def findMin(self, nums):
            if not nums:
                return -1
    
            low, high = 0, len(nums) - 1
            mid = (low + high) / 2
    
            while low < high:
                if nums[mid] > nums[mid + 1]:
                    return nums[mid + 1]
                if nums[mid] > nums[high]:
                    low = mid + 1
                elif nums[mid] > nums[low]:
                    high = mid
                else:
                    high -= 1
    
                mid = (low + high) / 2
    
            return nums[mid]

  • 1
    S

    This is not order O(logN) . It has O(N) worst case running time because in the else part of your loop , high is just decreased by 1. In the worst case this will always be the case . take the sequence :
    21222222222222222222222222222222222222222222.


Log in to reply
 

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