LeetCode-81. 搜索旋转排序数组 II

1、题目描述：

已知存在一个按非降序排列的整数数组 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,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

你必须尽可能减少整个操作步骤。

示例 1：

输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true

示例 2：

输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false

提示：

• 1 <= nums.length <= 5000
• -104 <= nums[i] <= 104
• 题目数据保证 nums 在预先未知的某个下标上进行了旋转
• -104 <= target <= 104

2、代码：

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        // 初始化左右指针
        int left = 0, right = nums.size() - 1, mid;
        
        // 当左指针不超过右指针时，继续二分查找
        while (left <= right) {
            // 计算中间位置
            mid = (left + right) / 2;
            
            // 如果中间元素等于目标值，直接返回 true
            if (nums[mid] == target) {
                return true;
            }
            
            // 处理重复元素的情况：当中间元素等于右边界元素时，无法判断哪一侧有序
            // 此时将右边界左移一位，逐步排除重复元素的影响
            if (nums[mid] == nums[right]) {
                --right;
            }
            // 判断右侧是否有序：如果中间元素小于右边界元素，则右侧是有序的
            else if (nums[mid] < nums[right]) {
                // 如果目标值在右侧有序区间内，则调整左边界到 mid+1
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                }
                // 否则目标值可能在左侧，调整右边界到 mid-1
                else {
                    right = mid - 1;
                }
            }
            // 判断左侧是否有序：如果中间元素大于右边界元素，则左侧是有序的
            else {
                // 如果目标值在左侧有序区间内，则调整右边界到 mid-1
                if (target < nums[mid] && target >= nums[left]) {
                    right = mid - 1;
                }
                // 否则目标值可能在右侧，调整左边界到 mid+1
                else {
                    left = mid + 1;
                }
            }
        }
        
        // 如果循环结束仍未找到目标值，返回 false
        return false;
    }
};

3、解题思路：

1. 初始化指针 ：设置左右指针left和right。
2. 循环条件 ：在left <= right时进行循环。
3. 中间点计算 ：计算中间点mid。
4. 直接命中 ：如果中间元素等于目标值，直接返回true。
5. 右侧有序判断 ：如果中间元素小于右边界元素，说明右侧是必定有序的，左侧未必有序。因为旋转后的数组由两个有序子数组组成。若中间元素小于右边界元素，则右侧子数组未被旋转点分割，保持有序。若目标值位于nums[mid]和nums[right]之间，则在右侧搜索；否则在左侧搜索。
6. 左侧有序判断 ：如果中间元素大于右边界元素，说明左侧是必定有序的，右侧未必有序。因为中间元素大于右边界元素，表明旋转点位于mid和right之间，左侧子数组未被旋转，保持有序。若目标值位于nums[left]和nums[mid]之间，则在左侧搜索；否则在右侧搜索。
7. 处理重复元素 ：当中间元素等于右边界元素时，右边界左移，以排除重复元素的影响。