Find Minimum In Rotated Sorted Array Ii - Leetcode Solution

Problem Statement: 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.

Example:

Input: nums = [2,2,2,0,1] Output: 0

Input: nums = [1,3,5] Output: 1

Input: nums = [10,1,10,10,10] Output: 1

Solution: A simple approach to solve this problem is to iterate over the array and find the minimum value. However, this approach has a worst time complexity of O(n).

Another efficient approach is to use binary search to find the minimum element. Since the given array is sorted and rotated, we can divide the array into two parts: one part is sorted in ascending order, and the other part is not. We can then use binary search to find the pivot point, which is the index where the sorted part ends and the unsorted part begins.

To handle the case where the array contains duplicates, we need to take one extra step. If the middle element is equal to the leftmost element, we can start a linear search from the leftmost index until we find the first element that is not equal to the middle element. Similarly, if the middle element is equal to the rightmost element, we can start a linear search from the rightmost index until we find the first element that is not equal to the middle element. By doing this, we can ensure that we always make progress towards finding the minimum element.

Code:

def findMin(nums): left = 0 right = len(nums) - 1

while left < right:
    mid = left + (right - left) // 2

    if nums[mid] > nums[right]:
        left = mid + 1
    elif nums[mid] < nums[right]:
        right = mid
    else:
        right -= 1

return nums[left]

1