> For the complete documentation index, see [llms.txt](https://code.taozirui.com/lc/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code.taozirui.com/lc/binary-search/find-minimum-in-rotated-sorted-array-ii.md).

# 154. Find Minimum in Rotated Sorted Array II

Suppose an array sorted in ascending order 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.

**Example 1:**

```
Input: [1,3,5]

Output: 1
```

**Example 2:**

```
Input: [2,2,2,0,1]

Output: 0
```

**Note:**

* This is a follow up problem to [Find Minimum in Rotated Sorted Array](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/).
* Would allow duplicates affect the run-time complexity? How and why? -This affects the worst case complexity to be O(n) since the each iteration the input size at worst only shrink one step (nums\[mid] == nums\[right])

**Thoughts:**

1. Handle duplicates: if (nums\[mid] == nums\[right], then nums\[mid] maintains the value and right can only reduce one. 

**Code**

```python
class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (right - left >> 1) + left
            if  nums[mid] < nums[right]:
                right = mid

            elif nums[mid] > nums[right]:
                left = mid + 1

            else:
                right -= 1


        return nums[left] # left = right
```