154. Find Minimum in Rotated Sorted Array II
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
[0,1,2,4,5,6,7] might become
Find the minimum element.
The array may contain duplicates.
Input: [1,3,5] Output: 1
Input: [2,2,2,0,1] Output: 0
- This is a follow up problem to Find Minimum in Rotated Sorted Array.
- Would allow duplicates affect the run-time complexity? How and why? -This affects the worst case complexity to be O(n) since the each iteration the input size at worst only shrink one step (nums[mid] == nums[right])
- Handle duplicates: if (nums[mid] == nums[right], then nums[mid] maintains the value and right can only reduce one.
class Solution(object): def findMin(self, nums): """ :type nums: List[int] :rtype: int """ left, right = 0, len(nums) - 1 while left < right: mid = (right - left >> 1) + left if nums[mid] < nums[right]: right = mid elif nums[mid] > nums[right]: left = mid + 1 else: right -= 1 return nums[left] # left = right