Python solution with detailed explanation


  • 0
    G

    Solution

    Find Minimum in Rotated Sorted Array https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

    Key insight is that if an array is rotated, then between the two sub-arrays around the mid point, the lowest element lies in the array which is out of order. Now there are three possibilities which are shown in the figures below. We observe that lowest element is the first element when all elements are sorted. Otherwise it is in the segment about the mid element which is unsorted.
    https://goo.gl/photos/3CJrFiV72te92xC88
    https://postimg.org/image/asbbeo2c9/.

    **What is a single condition that can discriminate between the three cases? **

    • if nums[mid] > nums[high] then minimum number is in right half, otherwise it is in left half (first two)
    • if minimum number must be in the right half, then we must do low = mid+1. Doing low = mid will result in infinite loop. Case: [2,1]
    class Solution(object):
        def findMin(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            low,high = 0, len(nums)-1
            while low < high:
                mid = low + (high-low)//2
                if nums[mid] > nums[high]:
                    low = mid + 1 # Note that mid+1 is important.
                else:
                    high = mid
            return nums[low]
    

    What if we used nums[low] < nums[mid] as the discriminating condition?

    • Note that this only helps distinguish 2 and 3 (from figure) and we need a special condition for case 1 when rotation is zero.
    • Note that we dont do low = mid+1. Case [2,1]
    • The stopping condition is again an array of length 2.
    class Solution(object):
        def findMin(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            low,high = 0, len(nums)-1
            if nums[low] <= nums[high]:
                return nums[low]
            while low < high:
                mid = low + (high-low)//2
                if nums[low] < nums[mid]:
                    low = mid
                else:
                    high = mid
            return nums[low+1]
    

    Another Approach
    We apply binary search and out stopping condition is an out of order array of length 2. The smallest element is then nums[high]. Do not forget to test for boundary condition that array is in order already.

    class Solution(object):
        def findMin(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            low,high = 0, len(nums)-1
            if nums[low] <= nums[high]:
                return nums[low]
            while high-low != 1:
                mid = low + (high-low)//2
                if nums[low] < nums[mid]:
                    low = mid
                else:
                    high = mid
            return nums[high]
    

Log in to reply
 

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