力扣_数组24—搜索旋转排序数组II-Toy模板网

这篇具有很好参考价值的文章主要介绍了力扣_数组24—搜索旋转排序数组II。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目

已知存在一个按非降序排列的整数数组 $n u m s$ ，数组中的值不必互不相同。

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

给你旋转后的数组 $n u m s$ 和一个整数 $t a r g e t$ ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 $n u m s$ 中存在这个目标值 $t a r g e t$ ，则返回 $t r u e$ ，否则返回 $f a l se$ 。

你必须尽可能减少整个操作步骤。文章来源地址https://www.toymoban.com/news/detail-806208.html

思路

相比于“搜索旋转排序数组I” 不同之处在于旋转前的数组不是严格单调的，也就是说数组中可能出现重复的元素
由于数组中有重复的元素，因此可能出现 $n u m s [pl] == n u m s [mi d] == n u m s [p r]$ 的情况，此时无法判断哪边的数组有序
若出现上述情况，只能将 $pl + +, p r - -$ ，继续判断
还有一个要注意的就是判断 $t a r g e t$ 是否在有序区间内时不仅要判断 $t a r g e t$ 和 $n u m s [mi d]$ 的关系，还要判断 $t a r g e t$ 和 $n u m s [pl / p r]$ 的关系

代码

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int pl = 0, pr = nums.size()-1;
        while(pl <= pr){
            int mid = (pl+pr)/2;
            if(nums[mid] == target){
                return true;
            }
            // 特殊情况
            if(nums[mid] == nums[pr] && nums[mid] == nums[pl]){
                pl++;
                pr--;
            }
            // 右边有序
            else if(nums[mid] <= nums[pr]){
                // 不能只判断target > nums[mid]  还要加上target <= nums[pr]的判断
                if(target > nums[mid] && target <= nums[pr]){
                    pl = mid + 1;
                }
                else{
                    pr = mid - 1;
                }
            }
            // 左边有序
            else if(nums[mid] >= nums[pl]){
                if(target < nums[mid] && target >= nums[pl]){
                    pr = mid - 1;
                }
                else{
                    pl = mid + 1;
                }
            }
        }
        return false;
    }
};