thesarfo

Reference

Minimum in a Rotated Sorted Array II

Finding the minimum of a rotated sorted array that may contain duplicates, shrinking the range when the sorted half is ambiguous.

views 0

Same problem as Minimum in a Rotated Sorted Array with duplicates allowed. (LeetCode 154) When nums[mid] == nums[high], we can’t tell which half is sorted, so shrink high by one to make progress without risking skipping the minimum.

class Solution(object):
    def findMin(self, nums):
        low, high = 0, len(nums) - 1


        while low < high:
            mid = (low + high) // 2


            if nums[mid] == nums[high]:
                # Can't determine the sorted half, so shrink from the right
                high -= 1
            elif nums[mid] <= nums[high]:
                # Right half is sorted, so minimum is on the left
                high = mid
            else:
                # Left half is sorted, so minimum is on the right
                low = mid + 1


        return nums[low]

Time: O(n) worst case (many duplicates forcing one-at-a-time shrinking), O(log n) best case (no duplicates). Space: O(1).