# 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)

Java