浅析：搜索旋转排序数组

33. 搜索旋转排序数组

153. 寻找旋转排序数组中的最小值

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

剑指 Offer 11. 旋转数组的最小数字

搜索旋转排序数组

题目详情可见 搜索旋转排序数组

遇到一道很有意思的题目，核心也是用二分搜索！关于二分搜索的技巧可见 二分搜索

本人一直在「收缩区间」处裹不清楚，直到看到了一句话就豁然开朗：旋转数组后，从中间划分，一定有一边是有序的

所以我们只需要判断哪边有序，然后判断是否在该有序区间内。如果不在，那么肯定在另一半区间内

xxxxxxxxxx
public int search(int[] nums, int target) {
    int n = nums.length, l = 0, r = n - 1;
    while (l < r) {
        // 这种取中间值对应向右收缩，即：l = m; r = m - 1;
        int m = l + r + 1 >> 1;
        if (nums[m] == target) return m;
        // 右边有序 (判断右边有序一定在前面，和上面取中间值匹配)
        if (nums[m] <= nums[r]) 
            // 目标值在右边
            if (nums[m] <= target && target <= nums[r]) l = m;
            else r = m - 1;
        } else {
            // 目标值在左边
            if (nums[l] <= target && target <= nums[m]) r = m;
            else l = m + 1;
        }
    }
    return nums[l] == target ? l : -1;
}

注意：if (nums[m] <= nums[r])一定需要包含=；如果没有包含，左区间收缩会出现错误

例如：nums = {3, 1}, target = 1

下面给出另外一种写法：

x
public int search(int[] nums, int target) {
    int n = nums.length;
    int l = 0, r = n - 1;
    while (l < r) {
        // 这种取中间值对应向右收缩，即：r = m; l = m + 1;
        int m = l + r >> 1;
        if (nums[m] == target) return m;
        // 左边有序 (判断左边有序一定在前面，和上面取中间值匹配)
        if (nums[l] <= nums[m]) {
            if (nums[l] <= target && target <= nums[m]) r = m;
            else l = m + 1;
        } else {
            if (nums[m] <= target && target <= nums[r]) l = m;
            else r = m - 1;
        }
    }
    return nums[l] == target ? l : -1;
}

寻找旋转排序数组中的最小值

题目详情可见 寻找旋转排序数组中的最小值、寻找旋转排序数组中的最小值 II、剑指 Offer 11. 旋转数组的最小数字

上面的三个题目基本上一模一样，所以放在一起

用l, r分别表示左右边界指针，mid = l - (l - r) / 2

如果nums[mid] > nums[r]，则最小值一定落在区间[mid + 1, r]中，如下图所示：

如果nums[mid] < nums[r]，则最小值一定落在区间[l, mid]中，如下图所示：

注意：此时是mid，而不是mid - 1，因为最小值可能在mid处取得，如下图所示：

如果nums[mid] = nums[r]，则最小值一定落在区间[l, mid]，但是问题在于应该如何收缩区间呢？答案为：r = r - 1

由于可能存在重复的元素，对于下图所示的情况，r = r - 1为无错过收缩，即最小值依然在[l, r - 1]中

如果r恰好就是最小值，那么r = r - 1后就刚好错过了最小值，即最小值不在[l, r - 1]中，如下图所示：

但是区间[l, r - 1]为单调递增，所以最终一定会收缩到区间[l, l - 1]时结束，即区间[0, -1]

由于nums[mid] = nums[r]，所以nums[l ... mid]一定都和nums[r]相等

下面给出详细代码：

xxxxxxxxxx
public int findMin(int[] nums) {
    int n = nums.length;
    int l = 0, r = n - 1;
    while (l < r) {
        int m = l + r >> 1;
        if (nums[m] == nums[r]) r--; // 如果没有重复值，把该判断去掉即可
        else if (nums[m] < nums[r]) r = m;
        else l = m + 1;
    }
    return nums[l];
}