【练习】【二分】力扣热题100 33. 搜索旋转排序数组

题目

在传递给函数之前，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。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 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

来源：力扣热题100 33. 搜索旋转排序数组

思路（注意事项）

用户代码的主要问题包括：

1. 数组越界访问：在mid为0时访问mid-1，或在mid为n-1时访问mid+1，导致数组索引越界，程序崩溃。

2. 逻辑条件错误：在判断左右部分是否有序时，条件可能不正确，导致错误地确定有序区间。

3. 循环结束后的处理：循环结束后没有检查剩下的元素是否是目标值，可能导致遗漏。

针对这些问题，我需要提出修改建议，修复越界问题，并调整条件判断逻辑，确保正确确定有序区间，并正确处理目标值的搜索范围。

修复思路如下：

1. 避免访问mid-1和mid+1，改用mid作为分界点。例如，判断左半部分是否有序的条件应该是nums[l] <= nums[mid]，而不是比较mid-1。

2. 在确定有序区间后，判断目标值是否在该区间内，并调整搜索范围。

3. 处理循环结束后的情况，检查最后剩下的元素是否是目标值。

4. 处理特殊情况，如数组长度为1的情况，避免越界访问。

纯代码

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size(), l = 0, r = n - 1;
        if (n == 0) return -1;

        while (l <= r)
        {
            int mid = l + r >> 1;
            if (nums[mid] == target) return mid;

            if (nums[l] <= nums[mid])
            {
                if (target < nums[mid] && target >= nums[l]) r = mid - 1;
                else l = mid + 1;
            }
            else
            {
                if (target <= nums[r] && target > nums[mid]) l = mid + 1;
                else r = mid - 1;
            }
        }

        return -1;
    }
};

题解（加注释）

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        if (n == 0) return -1;

        int left = 0, right = n - 1;

        // 标准二分查找模板
        while (left <= right) {
            int mid = left + right >> 1; 
            if (nums[mid] == target) return mid;

            // 判断左半部分是否有序
            if (nums[left] <= nums[mid]) {
                // 如果 target 在左半部分的有序区间内
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1;  // 缩小右边界
                } else {
                    left = mid + 1;    // 否则搜索右半部分
                }
            } 
            // 右半部分有序
            else {
                // 如果 target 在右半部分的有序区间内
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;   // 缩小左边界
                } else {
                    right = mid - 1;   // 否则搜索左半部分
                }
            }
        }

        return -1;  // 未找到目标值
    }
};