浅析：搜索旋转排序数组

搜索旋转排序数组

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

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

123

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


public int search(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left - (left - right) / 2;
        // 找到
        if (nums[mid] == target) return mid;
        // 左边有序
        if (nums[left] <= nums[mid]) {
            // target 在左边
            if (nums[left] <= target && target < nums[mid]) right = mid - 1;
            else left = mid + 1;
        } else {
            // target 在右边
            if (nums[mid] < target && target <= nums[right]) left = mid + 1;
            else right = mid - 1;
        }
    }
    return -1;
}

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

例如样例：nums = {3, 1}, target = 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 left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left - (left - right) / 2;
        if (nums[mid] > nums[right]) left = mid + 1;
        else if (nums[mid] < nums[right]) right = mid;
        else right -= 1;
    }
    return nums[left];
}