Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
Find the minimum element.
The array may contain duplicates.
Example 1:
Input: [1,3,5] Output: 1
Example 2:
Input: [2,2,2,0,1] Output: 0
Note:
The description was taken from https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/.
#O(Log(N)) Average, O(N) Worst Time, O(1) Spaceclass Solution: def findMin(self, nums: List[int]) -> int: left, right = 0, len(nums) - 1 while left < right: mid = (left + right) // 2 if nums[left] == nums[mid] == nums[right]: right -= 1 left += 1 elif nums[mid] <= nums[right]: right = mid else: left = mid + 1 return nums[left] We can solve this question using a binary search.
A clue that this algorithm can be utilized is if we are given a problem where either the input or the output is sorted, and we are looking for a specific target within that input or output.
Where we need to adjust a general binary search algorithm is where we decide to move the left and right pointers in each iteration. Typically, we would move these if the mean value is higher or lower than the target.
Here, we will need to move these in order to find the non-rotated portion of the array.
The only difference between this variation of the problem and the previous is the introduction of possible duplicate values. These won't pose a threat unless we get to a point where both our left, middle, and right pointers are on a duplicate value. If this is the case, we will move the left and right pointers inward to continue our search.
This is also the same trick to handle duplicates that can be utilized in Search in Rotated Sorted Array II.
We will start by initializing our left and right pointers to be the first and last elements of the array.
left, right = 0, len(nums) - 1
We are looking for the element that should be at the left-most position of the sorted array.
In our loop that we will run the left pointer is less than the right, we’ll set the middle pointer as the mean of the left and right positions.
while left < right: mid = (left + right) // 2
If all of the pointers share the same element value, we could have a test case like this because of duplicates:
If that is the case, then we would want to want to move both the left and right pointers inward to decrease the bounds of our search since our algorithm wouldn't really know whether to go left or right, but would know that the left and right pointers are not the target value.
We will check if the middle element is less than or equal to the right, they could be equal due to duplicates. If the array isn't rotated then we would expect the minimum to be the left-most position. If the middle element is less than the right then that means we're in a nonrotated portion of the array so we will move leftward as expected.
We could have a test case like the one shown below.
Otherwise, we are in a rotated portion of the array, so we will move the left pointer rightward so that we can move to the nonrotated portion of the array and continue searching for the minimum.
We could have a test case like the one shown below.
else: left = mid + 1
Once we have broken from our loop, we can return the element at our left or right pointer as it will be our minimum.
return nums[left]