Find Minimum in Rotated Sorted Array II

Problem Description

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. Given the sorted rotated array nums that may contain duplicates, return the minimum element of this array.

Key Insights

• The array is initially sorted but then rotated, which can disrupt the order.
• The presence of duplicates means that we cannot always determine which half of the array is sorted.
• A modified binary search approach can be used to efficiently find the minimum value.
• Even when duplicates are present, the algorithm needs to handle cases where both the left and right values are equal.

Space and Time Complexity

Time Complexity: O(n) in the worst case due to duplicates, but O(log n) on average for unique elements.
Space Complexity: O(1) since we are using a constant amount of space.

Solution

To solve this problem, we can implement a modified binary search algorithm. The key steps are:

1. Define two pointers, left and right, to represent the current search range.
2. While left is less than or equal to right:
   • Calculate the mid-point.
   • Compare the mid-point value with the rightmost value.
   • If the mid-point value is greater than the rightmost value, it indicates that the minimum must be in the right half. Move the left pointer to mid + 1.
   • If the mid-point value is less than the rightmost value, the minimum must be in the left half, so move the right pointer to mid.
   • If the mid-point value is equal to the rightmost value, we cannot determine the sorted half, hence decrement the right pointer to narrow the search.
3. The loop continues until the left pointer converges with the right pointer, at which point the minimum value is found.

Code Solutions