LC 153 - Find Minimum in Rotated Sorted Array

Question

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

• [4,5,6,7,0,1,2] if it was rotated 4 times.
• [0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

Example 1:

Input: nums = [3,4,5,1,2]
Output: 1

Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:

Input: nums = [4,5,6,7,0,1,2]
Output: 0

Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:

Input: nums = [11,13,15,17]
Output: 11

Explanation: The original array was [11,13,15,17] and it was rotated 4 times.

Constraints:

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• All the integers of nums are unique.
• nums is sorted and rotated between 1 and n times.

Links

Question here and solution here

Solution

concept

We use binary search on this problem despite the array is rotated: but part of the array is still sorted.
There are 2 parts of the array that is continuous, e.g. [3,4,5,1,2] has [3,4,5] and [1,2] and notice that the all elements in left part is always bigger than those in the right part due to rotation. We can use these properties.
Specifically, we still initialize l and r pointer as usual at the 2 ends of the array and we will maintain an ans variable to keep track the minimum value so far.

1. if nums[mid] >= nums[l], it means that nums[mid] belongs to the left portion and we should search right for smaller value (= because l and midcould be the same)
2. if the above is false, then we should search the left
3. if we notice nums[l] < nums[r] means we are already in an array that is already sorted, then nums[l] should be used to compare to the last updated ans to give the final answer (we could have overshot and the correct answer is already captured in ans).

Notice there is a variation of binary search called lower bound where we do not track ans separately and use while l < r. We update r = m such that we do not over step and skip.

code

class Solution:
    def findMin(self, nums: List[int]) -> int:
        l, r = 0, len(nums) - 1
        ans = float("inf")

        while l <= r:
            mid = (l + r)//2
            ans = min(ans, nums[mid])
            if nums[l] < nums[r]:
                return min(ans,nums[l])
                break
                
            elif nums[mid] >= nums[l]:
                l = mid + 1
            else:
                r = mid - 1

        return ans
        
class Solution:
	"""
	notice the l < r
	this is also called lower bound binary search
	"""
    def findMin(self, nums: List[int]) -> int:
        l, r = 0, len(nums) - 1
        while l < r:
            m = l + (r - l) // 2
            if nums[m] < nums[r]:
                r = m
            else:
                l = m + 1
        return nums[l]

Complexity

time: $O(\log n)$
space: $O(1)$