【面试算法专栏及回答思考】——搜索旋转排序数组

这是我参与11月更文挑战的第6天，活动详情查看：2021最后一次更文挑战

搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

示例 1：

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
复制代码

示例 2：

输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
复制代码

示例 3：

输入：nums = [1], target = 0
输出：-1
复制代码

提示：

• 1 <= nums.length <= 5000
• -10^4 <= nums[i] <= 10^4
• nums 中的每个值都 独一无二
• 题目数据保证 nums 在预先未知的某个下标上进行了旋转
• -10^4 <= target <= 10^4

进阶：

你可以设计一个时间复杂度为 O(log n) 的解决方案吗？

解题

解题思路

这道题考察的是二分法的灵活运用，简单的二分法就是设定一个left和right指针，并不断判断mid和目标值的大小关系。

在本题中，由于发生了旋转，只有一部分数组是有序的，因此需要提前加一个判断条件，每次都比较mid的值和right的值的大小关系。

二分查找。但是，旋转后，就成了两段有序数组。而二分法本质是判断 A or B，或者说 0 / 1 的判别。从而不断缩小搜索空间。只要能满足“二分”的本质，就可以尝试二分法解决问题。

该题虽然不是单调有序的数组。但它可以满足二分本质性质。可以通过一些条件，将搜索空间二分（搜前半段还是后半段）。

解题过程

首先通过mid位置的元素与数组的首元素（也可以选择尾元素），判别拐点的位置在mid的前还是后，从而得知[left,mid] or [mid,right]是单调的。本题采用数组首元素协助判别。

具体如下：

nums(mid) > nums(left)，则前半段[left,mid]是单调递增的，拐点在 后半段[mid,right]；
nums(mid) < nums(left)，则后半段 [mid,right]是单调递增的，拐点在前半段[left,mid]；
由<1>得知前[left,mid] 或 后[mid,right]的单调性后，再引入target与单调区间的边界值进行比较。具体步骤如下：
<2-1> 首先，target == nums(mid)直接返回结果；
<2-2> 假如，前半段[left,mid]单调，if (nums(left) <= target < nums(mid)，就在前半段[left,mid)找，即right = mid - 1；否则在(mid,right]找，即left = mid+1;
<2-3> 假如，后半段[mid,right]单调，if (nums(mid) < target <= nums(right)，就在后半段(mid,right]找，即left = mid + 1；否则在[left,mid)找，即right = mid-1;
如果全都没有找打，返回-1。

【注】细节上就是判别条件中到底是“>=”，还是“>"（亦或是“<=”还是“<”），带不带“=”号，需要注意。最好是拿几个示例推演几遍。

代码实现

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        int res = -1;
        int left = 0, right = n;
        while (left < right) {
            int mid = left + (right - left) / 2;
            // 找到
            if (nums[mid] == target) {
                res = mid;
                break;
            }
            // 左半有旋转部分，右半有序
            if (nums[mid] < nums[left]) {
                // 在右半
                if (nums[mid] < target && target <= nums[right-1]) {
                    left = mid + 1;
                } else { // 在左半
                    right = mid;
                }
            } else { // 左半无旋转部分，左半有序
                // 在左半
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid;
                } else { // 在右半
                    left = mid + 1;
                }
            }
        }
        return res;
    }
}
复制代码

当 nums[mid] == nums[left] 的时候，无法判断左半是否有旋转部分，无法确定是左半有序还是右半有序，只能收缩窗口大小1，即 left++，排除一个同nums[mid] 相等的数。

class Solution {
    public boolean search(int[] nums, int target) {
        int n = nums.length;
        int left = 0, right = n;
        while (left < right) {
            int mid = left + (right - left) / 2;
            // 找到
            if (nums[mid] == target) {
                return true;
            }
            // 无法判断左半是否有旋转部分，普通收缩
            if (nums[mid] == nums[left]) {
                left++;
                continue;
            }
            // 左半有旋转部分，右半有序
            if (nums[mid] < nums[left]) {
                // 在右半
                if (nums[mid] < target && target <= nums[right-1]) {
                    left = mid + 1;
                } else { // 在左半
                    right = mid;
                }
            } else { // 左半无旋转部分，左半有序
                // 在左半
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid;
                } else { // 在右半
                    left = mid + 1;
                }
            }
        }
        return false;
    }
}
复制代码

关于搜索旋转排序数组的思考和方法今天就分享到这里，同学想看到关于算法面试中的哪些疑难解析，可以给我留言，我们一起再来探讨，我们下篇文章再见。