AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

LeetCode 81. Search in Rotated Sorted Array II二分详细解法    原题链接    中等

作者: 作者的头像   T-SHLoRk ,  2019-07-13 23:30:22 ,  所有人可见 ,  阅读 3363


12


3

题目描述

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).

You are given a target value to search. If found in the array return true, otherwise return false.

题意:一个有序数组,将数组后面一部分元素移到数组最开始的地方,在这个数组中找到某个数是否存在。33题的加强版,允许有重复元素。因为涉及到精确值的查找,我们使用二分查找模板一 。

样例

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

算法1

我们知道,整个旋转后的数组由两个非严格单调递增的子数组组成,假设$[left,right]$是当前搜索空间。

  • 如果$nums[mid] > nums[left]$,说明$mid$在第一个非严格单调递增子数组中,那么$[left,mid]$这个区间肯定是非严格单调递增的。那么如果$target$在$[nums[left],nums[mid])$这个区间内,那么搜索范围就会变成$[left,mid-1]$。
  • 如果$nums[mid] < nums[left]$,说明$mid$在第二个非严格单调递增子数组中,那么$[mid,right]$这个区间肯定是非严格单调递增的。那么如果$target$在$(nums[mid],nums[right])$这个区间内,那么搜索范围就会变成$[mid+1,right]$。
  • 最后一种情况则是最复杂的。如果$nums[mid]=nums[left]$,那么$mid$既有可能在第一个区间内(从$left$到$mid$的数都相等),也有可能在第二个区间内(从$mid$到$right$的值都相等,且等于$left$)。假设原数组是[1,2,3,3,3,3,3],那么旋转之后有可能是[3,3,3,3,3,1,2],或[3,1,2,3,3,3,3]。这个时候,其实我们只需要将$left = left + 1$就可以了,因为$nums[left] = nums[mid],nums[mid] != target$,那么$nums[left]!=target$,所以我们可以将搜索范围缩小。

@yxc说过他想到的二分解法在最坏情况下会退化成$O(n)$的时间复杂度,的确如此,考虑一个全是1的数组,$target = 0$,任何时候$nums[mid] = nums[left]$,每次只会$left =left +1 $退化成线性复杂度。

我认为二分的边界转换就是不断的排除不可能的解,留下潜在的可行解。只要分析好在不同的情况,解空间会在什么范围内就一定不会把边界弄错。

C++ 代码

    bool search(vector<int>& nums, int target) {
        int n = nums.size();
        if (n == 0) return false;
        int left = 0, right = n - 1;
        while(left <= right)
        {
            int mid = (left + right) / 2;
            if(nums[mid] == target) return true;
            else if(nums[mid] > nums[left])//左半区间非严格单调递增
            {
                //target是否在左半区间内
                if(target >= nums[left] && target < nums[mid]) right = mid - 1;
                else left = mid + 1;
            }else if(nums[mid] < nums[left])//右半区间严格单调递增
            {
                //target是否在右半区间内
                if(target > nums[mid] && target <= nums[right]) left = mid + 1;
                else right = mid - 1;
            }
            else//只能排除left不是一个可行解
                left++;
        }
        return false;
    }

2 评论


用户头像
yxc   2019-07-13 23:38      1    踩      回复

棒!


用户头像
刘洪宇   2021-12-23 10:50         踩      回复

贼棒


App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息