leetcode Java：154. 寻找旋转排序数组中的最小值 II

题目：154. 寻找旋转排序数组中的最小值 II

思路：二分。

与上一题不同的是，数组可以重复，那么旋转之后，可以以旋转点分成左右两个有序数组，且左侧数组中的元素一定大于等于右侧数组中的元素。

二分时分为以下几种情况：

1. nums[mid] > nums[right]

   ：说明

   mid

   在左侧数组，此时移动

   left

   ，

   left = mid + 1

   ；

2. nums[mid] < nums[right]

   ：说明

   mid

   在右侧数组，此时移动

   right

   ，注意，

   right = mid

   ，因为存在

   mid

   即是最小值的情况；

3. nums[mid] == nums[right]

   ：此时无法判定

   mid

   在哪里，不过可以左移一位

   right

   ，因为

   right

   处的值与

   mid

   相等，不会丢失解。

最后，

left

会与

right

相遇，这就是我们要求的解。

代码：

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