# 0154. Find Minimum in Rotated Sorted Array II
###### tags: `Leetcode` `Hard` `Binary Search`
Link: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/description/
## 思路
第一种情况```nums[mid] > nums[right]```可以轻易判断出mid在左区间。

第二种情况```nums[mid] < nums[right]```可以轻易判断出mid和right在同一个区间。考虑到我们始终往右区间收敛，所以可以判定此时mid在右区间。

第三种情况，有一个非常tricky的技巧。既然无法判定mid是否在左区间还是右区间，但是因为nums[mid]和nums[right]一样，那么去掉nums[right]并不影响结果。去掉nums[right]（将右边界左移一位）反而可以进一步帮助分析mid所属的位置：如果下一步出现nums[mid]和nums[right]不一样，那就依照之前的逻辑很好处理；否则就继续移动right，同样没有影响。
## Code

class Solution {
    public int findMin(int[] nums) {
        int n = nums.length;
        int left = 0, right = n-1;
        while(left<right){
            int mid = left+(right-left)/2;
            if(nums[mid]<nums[right]) right = mid;
            else if(nums[mid]>nums[right]) left = mid+1;
            else right--;
        }
        return nums[left];
    }
}