[LeetCode81.搜索旋转排序数组 II]｜刷题打卡

一、题目描述：

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。

编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 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 可能包含重复元素。
2. 这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？

相关知识：二分查找。

二、思路分析：

考察点与思想

这道题考察的点是算法里面比较常见的二分查找，但是对题目的难度进行加深。如果用暴力法解是很容易的，直接遍历就行，但是不能达到对时间复杂度的要求。所以我们考虑二分法，我们先来看看二分法的核心解题思想。

解题思想：

1. 预处理-如果待求解数组未排序，则需要考虑先进行排序；
2. 二分查找-使用循环或递归在每次比较后将查找空间划分为两半；
3. 后处理-继续在剩余空间中确定可行的候选者。

思路和问题

总归一句话，二分法达到的目的就是每次处理后都能将问题处理规模折半。

在这一题中，数组是旋转排序的，我们在使用二分时，乍一看好像要先把数组重新排序，但其实不用，有一个关键点：分成两个数组后，肯定会有一个数组是严格排好序的，那我们可以判断目标值是否在这个排好序的数组中，如果不在，那就肯定在另一个数组。在实际处理过程中也要注意数组有可能存在重复元素的情况。

大体思路如下：

1. 每次都判断目标值在哪个区间，直到l>r；
2. 每次都必定有一边有序
3. 若nums[l] < nums[m],nums[l]<= target < nums[m],则在左边有序组,收缩右边界；
4. 若nums[l] > nums[m],nums[m]< target < nums[l],则右边有序,收缩左边界；
5. 若nums[l] == nums[m], 则不确定，l右移

三、AC 代码：

bool search(int* nums, int numsSize, int target){
    int l = 0;
    int r = numsSize - 1;
    int m = 0;
    while(l <= r) {
        m = l + ((r-l) >> 1);
        if(target == nums[m]) return true;
        if(nums[l] < nums[m]) {
            if(nums[l] <= target && target < nums[m]) {
                r = m - 1;
            }else {
                l = m + 1;
            }
        }else if(nums[l] > nums[m]) {
            if(nums[m] < target && target < nums[l]) {
                l = m + 1;
            }else {
                r = m - 1;
            }
        }else {
            l++;
        }
    }
    return false;
}

四、总结：

这个算法是对二分查找应用的进阶版，通过寻找目标值得到求解。

在涉及二分法处理的题中，无论怎么变，都是万变不离其宗，都是从核心思想入手，尽量在每次处理后都将问题的规模缩小到原来的一半，直到得到满足条件的解或者超出边界。

本文正在参与「掘金 2021 春招闯关活动」, 点击查看 活动详情