Find Minimum in Rotated Sorted Array
Medium
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 rotated4times.[0,1,2,4,5,6,7]if it was rotated7times.
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.
Solution
Brute Force Solution
The most straightforward approach is to iterate through the array and find the minimum element. This will work regardless of how many times the array has been rotated.
Code
def find_min_brute_force(nums):
min_val = nums[0]
for i in range(1, len(nums)):
if nums[i] < min_val:
min_val = nums[i]
return min_val
Time Complexity
O(n), where n is the length of the array, as we iterate through each element once.
Space Complexity
O(1), as we only use a constant amount of extra space to store the minimum value.
Optimal Solution: Binary Search
Since the array is sorted (before rotation), we can use binary search to find the minimum element in O(log n) time. The key idea is to check if the array is rotated by comparing the first and last elements. If nums[left] < nums[right], then the array is not rotated, and the minimum element is simply nums[left]. Otherwise, we proceed with binary search.
In the binary search, we check if the middle element is greater than the rightmost element. If it is, then the minimum element must be in the right half of the array. Otherwise, the minimum element must be in the left half (including the middle element).
Code
def find_min_binary_search(nums):
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2 # Prevent potential overflow
if nums[mid] > nums[right]:
left = mid + 1
else:
right = mid
return nums[left]
Time Complexity
O(log n), where n is the length of the array, due to the binary search.
Space Complexity
O(1), as we only use a constant amount of extra space for pointers.
Edge Cases
- Empty array: The problem states that
1 <= n <= 5000, so we don't need to handle an empty array. - Single element array: The algorithm works correctly for an array with one element.
- Array not rotated: The algorithm correctly identifies the minimum element when the array is not rotated (i.e., when it's already sorted in ascending order).
