Leetcode #153 Find Minimum in Rotated Sorted Array

This Problem we are trying to find mininum value from Rotated Sorted Array.

For example, if there is an array [0, 1, 2, 3, 4, 5, 6, 7] that is already sorted it gets rotated by random number n.

 

Case A

If the array is [4, 5, 6, 7, 0, 1, 2, 3] it rotated 4 times.

 

What we need are mid point, most left point, and most right point.

 

1. In this case mid point become 7 and we knows that the mid point is larger than most left point which means we can eliminate everthing up to mid point and move most left point to 0.

 

after that the array would look like this

[4, 5, 6, 7, 0, 1, 2, 3] 

 

2. Now we only care about  0, 1, 2, 3

 

which is already sorted which means, we can compare most left and most right and give it the result back.

 

Case B

 

if the array rotated like [6, 7, 0, 1, 2, 3, 4, 5] which is 2 times,

 

1. Mid point becomes 4 and we knows that mid point 1 is smaller than most left point 6 which means we are going to eliminate everthing right after midpoint 1.

 

After that the array would look like this

[6, 7, 0, 1, 2, 3, 4, 5]

 

2. Now we do the same thing again. mid point becomes 7 ( (left + right) // 2 ) and we can eliminate 6, 7

 

3 After that the array would look like this

 

[6, 7, 0, 1, 2, 3, 4, 5]

 

Array already sorted we need to see if the most left is smaller than what we save as result.

 

 

class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        left, right = 0, len(nums) - 1
        # Save any number to res for convenient reason we put most left to res.
        res = nums[0]
        while left <= right:
            # if the array we are searching is sorted.
            if nums[left] < nums[right]:
                res = min(res, nums[left])
                break

            mid = (left + right) // 2

            #checking if the mid point is smaller than what we saved in res. 
            # for case such as [3, 1, 2]
            res = min(res, nums[mid])

            if nums[mid] >= nums[left]:
                left = mid + 1
            else:
                right = mid - 1
        
        return res