LC 0154 [H] Find Minimum in Rotated Sorted Array II - ALawliet/algorithms GitHub Wiki
first binary search but check the == case for duplicate and decrement
class Solution:
def findMin(self, nums: List[int]) -> int:
l, r = 0, len(nums) - 1
while l < r:
m = (l + r) // 2
if nums[m] > nums[r]:
l = m + 1
elif nums[m] < nums[r]:
r = m
else:
r -= 1
return nums[l]
^ this finds the correct min value but the wrong min index
to find the correct min index too:
class Solution:
def findMin(self, nums: List[int]) -> int:
l, r = 0, len(nums) - 1
while l < r:
m = (l + r) // 2
if nums[m] > nums[r]:
l = m + 1
elif nums[m] < nums[r]:
r = m
else:
if nums[r-1] > nums[r]: l = r ; break # add this
r -= 1
return nums[l]