**Solution with discussion** https://discuss.leetcode.com/topic/76088/python-solution-with-detailed-explanation

**Find Minimum in Rotated Sorted Array II** https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/

**Problem Background**

- Follow up from question to find minimum where you have no duplicates: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
- Give an example where we fail our algorithm findmin? [3,1,3]
- Why cant we have a Lg(N) solution? https://postimg.org/image/asbbeo2c9/ and explanation is: https://discuss.leetcode.com/topic/5182/rough-sketch-of-proof-why-o-lg-n-is-impossible/2
- The reason is that we can hit a case where nums[mid] is same as nums[high] and then we need to reduce [2,2,1,2]

**Algorithm**

- Modification is minor - account for the case when nums[mid] equals nums[high].
- Safest solution here is to reduce high by 1: high = high-1. This is findMin_init.

```
class Solution(object):
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
low,high = 0,len(nums)-1
while low < high:
mid = low + int((high-low)/2)
if nums[mid] > nums[high]:
low = mid + 1
elif nums[mid] < nums[high]:
high = mid
else: # nums[mid] == nums[high]
high = high - 1
return nums[low]
```

- Optimized is when nums[low]=nums[mid]=nums[high], then increase low by 1 and reduce high by 1 otherwise high = mid.
- Now last condition here can be sketched nicely - increasing and then plateaus.
- Check this: https://goo.gl/photos/5xG7nmh3wNZfJAz1A

```
class Solution(object):
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
low,high = 0,len(nums)-1
while low < high:
mid = low + int((high-low)/2)
if nums[mid] > nums[high]:
low = mid + 1
elif nums[mid] < nums[high]:
high = mid
else: # nums[mid] == nums[high]
if nums[mid] == nums[low]:
low, high = low + 1, high - 1
else:
high = mid
return nums[low]
```