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