Clean and Simple Classic Binary Search with O(n) time and O(1) Space, with explanation


  • 0
    P
    class Solution(object):
        def findMin(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            # always compare nums[mid] to nums[r] to shrink the range which min. stays.
            # three cases:
            # 1. nums[mid] == nums[r]: only to know nums[r] is not min
            # 2. nums[mid] > nums[r]: as the rotation rule´╝înums[l] cannot be lower than nums[r], so search right
            # 3. nums[mid] < nums[r]: as the rotation process, it is impossible to have a value x s.t.  x < nums[mid] < nums[r], so search left
            l, r = 0, len(nums)-1
            while l < r:
                mid = (l+r)/2
                if nums[mid] == nums[r]:
                    r -= 1  
                elif nums[mid] < nums[r]:
                    r = mid
                else:
                    l = mid + 1
            return nums[l]
    

Log in to reply
 

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