Can Python solve this problem in O(lgn)?


  • 0
    A

    Because we don't know the size. If we use len(nums), which would cause O(N), right?

    Then there's no way we can solve this problem in O(lg n) in Python!?

    Here's my AC code:

    class Solution:
    # @param {integer[]} nums
    # @return {integer}
    def findMin(self, nums):
        beg = 0
        end = len(nums)-1
        while end>beg:
            mid = (beg+end)/2
            if nums[beg] <= nums[mid] and nums[mid] <= nums[end]:
                return nums[beg]
            if nums[mid] <= nums[beg] and nums[mid] <= nums[end]: # max, min, mid
                end = mid
            if nums[beg] <= nums[mid] and nums[mid] >= nums[end]: # mid, max, min
                beg = mid+1
                
        return nums[beg]

Log in to reply
 

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