Find Minimum in Rotated Sorted Array

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.

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.

Despite the drawback of rotations, the array still preserves a lot of its order that we can exploit. Rotations effectively split the array into two sections: a higher order section followed by a lower order section. Since they are still both ordered, we can use this fact to deduce where the minimum element would be.

Suppose we have the array [0, 1, 2, 3, 4, 5, 6, 7] rotated 2 times, becoming [6, 7, 0, 1, 2, 3, 4, 5]. Now suppose we pick a random element - for argument’s sake, we choose 3. Consider the elements of the array to the left and right: we have a subarray [6, 7, 0, 1, 2, 3] on the left, and [4, 5] on the right. Since the array is still sorted somewhat, we know that the minimum element must be in the left subarray: the right subarray would only contain numbers bigger than 3 and less than 5, so the minimum element, if it was smaller than 3, must be in the left subarray. The rightmost element of each subarray gives us a bound on the minimum element!

This argument still works in the opposite manner: suppose we have the rotated array [2, 3, 4, 5, 6, 7, 0, 1], and we pick 5, giving us the subarrays [2, 3, 4, 5] and [6, 7, 0, 1]. Since 1 < 5, we know that the minimum element must exist in the right subarray as it contains elements bigger than 5 and smaller than 1. We can then repeat this until there is only one element in the subarray, containing our answer.

What is the most effective element to pick at each step? We want to reduce our search space in the next step as much as possible, and since the minimum element could be in either subarray, the best we can do is halving the search space. This is binary search!

def findMin(self, nums: List[int]) -> int:
    l, r = 0, len(nums) - 1

    while l < r:
        mid = (l + r) // 2
        if nums[mid] < nums[r]:
            r = mid
        else:
            l = mid + 1

    return nums[l]    

Time Complexity

Other than the initial assignment statement and the final return statement that are both constant time, the only operations take place in the while loop. Since we are always dividing the search area in 2, we have $\log_2 n$ division, and since each iteration is constant time, we have $\mathcal{O}(\log n)$ time.

Space Complexity

Since only constant variables are used, the time complexity is constant.