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.
For example:
Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.
As another example:
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.
Write a function to efficiently find the minimum element in a rotated sorted array.
Solution
Brute Force Solution
The simplest approach is to iterate through the array and find the minimum element. This involves comparing each element with the current minimum and updating the minimum if a smaller element is found.
Code
def find_min_brute_force(nums):
min_val = nums[0]
for num in nums:
if num < min_val:
min_val = num
return min_val
Time Complexity
The time complexity of this approach is O(n), as we need to iterate through all the elements in the array once.
Space Complexity
The space complexity is O(1) because we only use a constant amount of extra space to store the minimum value.
Optimal Solution: Binary Search
Since the array is sorted and rotated, we can use binary search to find the minimum element in O(log n) time.
Algorithm
- Initialize
left = 0andright = nums.length - 1. - While
left < right:- Calculate
mid = left + (right - left) // 2to prevent overflow. - If
nums[mid] > nums[right], it means the minimum element is in the right half of the array. So, updateleft = mid + 1. - Otherwise, the minimum element is either
nums[mid]or in the left half. So, updateright = mid.
- Calculate
- The minimum element is
nums[left].
Code
def find_min_binary_search(nums):
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] > nums[right]:
left = mid + 1
else:
right = mid
return nums[left]
Time Complexity
The time complexity of this binary search approach is O(log n), where n is the number of elements in the array. This is because we are dividing the search space in half at each step.
Space Complexity
The space complexity is O(1) as we only use a constant amount of extra space to store variables like left, right, and mid.
Edge Cases
- Empty Array: The problem statement says 1 <= n <= 5000 so we don't need to consider empty array.
- Single Element Array: The algorithm works correctly for an array with a single element.
- Already Sorted Array: If the array is already sorted (not rotated), the algorithm will still correctly identify the first element as the minimum because the
right = midcondition will eventually makeleftpoint to the first element. - Duplicate elements: The prompt specified unique elements.
