154. 尋找旋轉排序數組中的最小值 II（困難題）

題目描述：

假設按照升序排序的數組在預先未知的某個點上進行了旋轉。

( 例如，數組 [0,1,2,4,5,6,7] 可能變為 [4,5,6,7,0,1,2] )。

請找出其中最小的元素。

注意數組中可能存在重複的元素。

示例 1：

輸入: [1,3,5]

輸出: 1

示例 2：

輸入: [2,2,2,0,1]

輸出: 0

說明：

這道題是 尋找旋轉排序數組中的最小值 的延伸題目。
允許重複會影響算法的時間複雜度嗎？會如何影響，為什麼？
           

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

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

思路概述：

使用二分思想，mid位置的值，如果比右邊界（right）的值大，則代表左半部分不會有最小值，讓 left = mid + 1.

如果不比右邊界的值大，則代表從mid到right是遞增的。此時再看mid和左邊界（left）哪個位置的大，如果mid位置的值更大，則代表從left到mid也是遞增的，那麼left對應的值就是最小值，直接傳回。

如果mid位置的值比left位置的值小，此時無法判斷遞增是在哪個位置中斷的，但是我們可以确定右邊界是個較大值，将右邊界舍去，right減一。