Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,4,4,5,6,7] might become:
[4,5,6,7,0,1,4] if it was rotated 4 times. [0,1,4,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 that may contain duplicates, return the minimum element of this array. You must decrease the overall operation steps as much as possible.
Example 1: Input: nums = [1,3,5] Output: 1 Example 2: Input: nums = [2,2,2,0,1] Output: 0
- code
class Solution:
def findMin(self, nums: List[int]) -> int:
low = 0
high = len(nums)-1
while high > low:
pivot = low + (high - low) // 2
# risk of overflow: pivot = (low + high) // 2
# Case 1):
if nums[pivot] < nums[high]:
high = pivot
# alternative: high = pivot - 1
# too aggressive to move the `high` index,
# it won't work for the test case of [3, 1, 3]
# Case 2):
elif nums[pivot] > nums[high]:
low = pivot + 1
# Case 3):
else:
high -= 1
# the 'low' and 'high' index converge to the inflection point.
return nums[low]
- code
class Solution:
def findMin(self, nums: List[int]) -> int:
l, r = 0, len(nums) - 1
res = nums[0]
while l <= r:
mid = l + (r-l) // 2
if nums[l] < nums[mid]: # left sorted
res = min(res, nums[l])
l = mid
elif nums[mid] < nums[r]: # right sorted
res = min(res, nums[mid])
r = mid - 1
else:
return min(res, min(nums[l:r+1]))
return res