# Question

Formatted question description: https://leetcode.ca/all/154.html

Follow up for "Find Minimum in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?
Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.

@tag-array


# Algorithm

When there are a large number of repeated numbers in the array, the mechanism of binary search will be destroyed, the time complexity of O(lgn) will not be obtained, and the simple and crude O(n) will be returned.

For example, these two situations: {2, 2, 2, 2, 2, 2, 2, 2, 0, 1, 1, 2} and {2, 2, 2, 0, 2, 2, 2, 2, 2, 2, 2, 2}, it can be found that when the first number, the last number, and the middle number are all equal, the binary search method collapses, because it cannot determine whether to go to the left half or the right half.

In this case, move the right pointer one place to the left (or move the left pointer one place to the right) to skip the same number, which will not affect the result, because it just removes the same one, and then affects the remaining part Continue to use the binary search method,

In the worst case, such as all elements of the array are the same, the time complexity will rise to O(n).

# Code

• 
public class Find_Minimum_in_Rotated_Sorted_Array_II {

public class Solution_II {
public int findMin(int[] nums) {

if (nums == null || nums.length == 0) {
return 0;
}

int low = 0; // left pointer
int high = nums.length - 1; // right pointer

//  while (low < high) {
while (low < high && nums[low] >= nums[high]) { // @note:@memorize: if no "=", failed by [3,1,3]

int mid = low + (high - low) / 2;
System.out.println("mid: " + nums[mid] + ", high: " + nums[high]);
if (nums[mid] > nums[high]) {
low = mid + 1;
} else if (nums[mid] < nums[low]) { // @note: in part-I, only else, no check, but if duplicates, then not working
high = mid; // @note: here, not "high=mid-1"
} else {
right--;
}
}

return nums[low];
}
}

public class Solution {
public int findMin(int[] nums) {

if (nums == null || nums.length == 0) {
return 0;
}

int low = 0; // left pointer
int high = nums.length - 1; // right pointer

//  while (low < high && nums[low] > nums[high]) {
while (low < high && nums[low] >= nums[high]) { // @note:@memorize: if no "=", failed by [3,1,3]

int mid = low + (high - low) / 2;
System.out.println("mid: " + nums[mid] + ", high: " + nums[high]);
if (nums[mid] > nums[high]) {
low = mid + 1;
} else if (nums[mid] < nums[high]) { // @note: in part-I, only else, no check, but if duplicates, then not working
high = mid; // @note: here, not "high=mid-1"
} else {
high--;
}
}

return nums[low];
}
}
}

• Todo

• class Solution:
def findMin(self, nums: List[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) >> 1
if nums[mid] > nums[right]:
left = mid + 1
elif nums[mid] < nums[right]:
right = mid
else:
right -= 1
return nums[left]

############

class Solution(object):
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
ans = nums
start, end = 0, len(nums) - 1
while start + 1 < end:
mid = start + (end - start) / 2
if nums[start] < nums[mid]:
start = mid
elif nums[start] > nums[mid]:
end = mid
else:
start += 1
ans = min(ans, nums[start])

return min(ans, nums[start], nums[end])