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

方法一：由 33.搜索旋转排序数组 和 81.搜索旋转排序数组II 引申出的二分

旋转排序数组的一个特点就是：一分为二，必定有一部分是有序的，另一部分可能是有序也可能是无序的。那有序部分的最小值一定就是该部分最左侧的元素，记录一下然后再去右侧探索，看是否有更小的值。因为这道题也是存在重复元素的，无法判断左侧还是右侧有序，所以和81题一样，让左右指针向中间收缩。

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

方法二：根据旋转排序数组两部分进行二分。

旋转排序数组由两个子数组nums1和nums2组成，nums1中的每个值都大于等于nums2中的每个值，这道题就需要搜索第二个数组的第一个位置。

假设nums[mid] 是二分查找时的中间值：

• 如果nums[mid] > nums[right]，那么说明mid在第一段数组，需要将下一次的搜索区间定在mid右侧
• 如果nums[mid] < nums[right]，那么说明mid在第二段数组，需要将下一次搜索区间定在mid及其左侧（因为mid可能就是第二段数组的第一个位置）
• 如果nums[mid] = nums[right]，这个时候其实是无法判断mid是在第一个区间还是第二个区间的
  • 假设nums[right]所对应的值就是最小值：
    • 因为mid的计算方式决定了mid一定是偏向于左侧的，所以mid必然不可能等于right，这时将right左移，缩小查找区间，最小值并不会被移出去，这时再继续判断就可以了
  • 假设最小值是在区间内
    • 那么right左移，并不会把最小值移出区间，所以也是没问题的