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];
    }
}