LeetCode刷题Java版033.搜索旋转排序数组

作者：沉默王二
发布时间：2022-08-27T18:28:48.115+0800

---

033.搜索旋转排序数组

题意

整数数组 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,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

难度

中等

示例

输入：nums = [4,5,6,7,0,1,2], target = 0

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

分析

我们知道，在一个有序的数组里面去判断一个数是否存在，可以利用二分查找。

但这题只是部分有序，或者说，是一个分开有序的数组，要怎么去判断呢？

想一下。

我们从任意一个位置将这个部分有序的数组分开，那么分开之后的两部分必然有一部分是有序的！

比如

nums = [4,5,6,7,0,1,2]      

nums = [4,5] [6,7,0,1,2]    breakPos = 2nums = [4,5,6] [7,0,1,2]    breakPos = 3nums = [4,5,6,7] [0,1,2]    breakPos = 4nums = [4,5,6,7,0] [1,2]    breakPos = 5nums = [4,5,6,7,0,1] [2]    breakPos = 6 

来看看分开之后的两部分，是不是至少有一部分是有序的？

那么我们是不是就能够在这有序的部分中去寻找target？

可以是可以，但是这样子的时间复杂度并非是二分查找的，而是要加上枚举breakPos位置的部分，合起来的时间复杂度就是，显然不太符合题目的要求。

想一想之前的过程，是不是有大量重复的计算量消耗在了不同的二分中呢？

比如我们在breakPos = 1,2,3,4的时候，如果target为4-7，是不是都要重复的去二分？

那能不能直接对这个breakPos进行二分呢？

可以！

考虑这样子的思路：

• 如果[lef,breakPos - 1]是有序的，而且nums[lef] <= target && target < nums[breakPos]，那么答案肯定是存在于[lef,breakPos - 1]，调整上界rig到breakPos - 1。
• 如果[breakPos，rig]是有序的，而且nums[breakPos] < target && target <= nums[rig]，那么答案肯定是存在于[breakPos,rig]中，调整下界lef到breakPos即可。

所以我们就可以直接在二分breakPos的时候，判断target是否存在了。

class Solution {

        int siz = nums.length;        int lef = 0,rig = siz - 1;        while(lef <= rig){            int mid = (lef + rig) >> 1;            if(nums[mid] == target)                return mid;            if(nums[0] <= nums[mid]){                if(nums[0] <= target && target < nums[mid])                    rig = mid - 1;                else                    lef = mid + 1;            }            else{                if(nums[mid] < target && target <= nums[siz - 1])                    lef = mid + 1;                else                    rig = mid - 1;            }        }        return -1;    }}

时间复杂度是，因为我们只需要二分breakPos，效率自然也不负所望。

总结

本题其实还是一个二分查找的模型，只是我们需要对二分之后两边的边界进行分类讨论，当一道题目是有序的或者说有着明确的大小关系，我们就可以向二分的方向去想，类似的还有像最小值最大化，或者最大值最小化这些情况，都是一些经典的二分思想的应用场景。

力扣链接：https://leetcode.cn/problems/search-in-rotated-sorted-array/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 710 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

033.搜索旋转排序数组

题意

整数数组 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,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

难度

中等

示例

输入：nums = [4,5,6,7,0,1,2], target = 0

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

分析

我们知道，在一个有序的数组里面去判断一个数是否存在，可以利用二分查找。

但这题只是部分有序，或者说，是一个分开有序的数组，要怎么去判断呢？

想一下。

我们从任意一个位置将这个部分有序的数组分开，那么分开之后的两部分必然有一部分是有序的！

比如

nums = [4,5,6,7,0,1,2]      

nums = [4,5] [6,7,0,1,2]    breakPos = 2nums = [4,5,6] [7,0,1,2]    breakPos = 3nums = [4,5,6,7] [0,1,2]    breakPos = 4nums = [4,5,6,7,0] [1,2]    breakPos = 5nums = [4,5,6,7,0,1] [2]    breakPos = 6 

来看看分开之后的两部分，是不是至少有一部分是有序的？

那么我们是不是就能够在这有序的部分中去寻找target？

可以是可以，但是这样子的时间复杂度并非是二分查找的，而是要加上枚举breakPos位置的部分，合起来的时间复杂度就是，显然不太符合题目的要求。

想一想之前的过程，是不是有大量重复的计算量消耗在了不同的二分中呢？

比如我们在breakPos = 1,2,3,4的时候，如果target为4-7，是不是都要重复的去二分？

那能不能直接对这个breakPos进行二分呢？

可以！

考虑这样子的思路：

• 如果[lef,breakPos - 1]是有序的，而且nums[lef] <= target && target < nums[breakPos]，那么答案肯定是存在于[lef,breakPos - 1]，调整上界rig到breakPos - 1。
• 如果[breakPos，rig]是有序的，而且nums[breakPos] < target && target <= nums[rig]，那么答案肯定是存在于[breakPos,rig]中，调整下界lef到breakPos即可。

所以我们就可以直接在二分breakPos的时候，判断target是否存在了。

class Solution {

        int siz = nums.length;        int lef = 0,rig = siz - 1;        while(lef <= rig){            int mid = (lef + rig) >> 1;            if(nums[mid] == target)                return mid;            if(nums[0] <= nums[mid]){                if(nums[0] <= target && target < nums[mid])                    rig = mid - 1;                else                    lef = mid + 1;            }            else{                if(nums[mid] < target && target <= nums[siz - 1])                    lef = mid + 1;                else                    rig = mid - 1;            }        }        return -1;    }}

时间复杂度是，因为我们只需要二分breakPos，效率自然也不负所望。

总结

本题其实还是一个二分查找的模型，只是我们需要对二分之后两边的边界进行分类讨论，当一道题目是有序的或者说有着明确的大小关系，我们就可以向二分的方向去想，类似的还有像最小值最大化，或者最大值最小化这些情况，都是一些经典的二分思想的应用场景。

力扣链接：https://leetcode.cn/problems/search-in-rotated-sorted-array/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 710 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

033.搜索旋转排序数组

题意

整数数组 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,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

难度

中等

示例

输入：nums = [4,5,6,7,0,1,2], target = 0

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

分析

我们知道，在一个有序的数组里面去判断一个数是否存在，可以利用二分查找。

但这题只是部分有序，或者说，是一个分开有序的数组，要怎么去判断呢？

想一下。

我们从任意一个位置将这个部分有序的数组分开，那么分开之后的两部分必然有一部分是有序的！

比如

nums = [4,5,6,7,0,1,2]      

nums = [4,5] [6,7,0,1,2]    breakPos = 2nums = [4,5,6] [7,0,1,2]    breakPos = 3nums = [4,5,6,7] [0,1,2]    breakPos = 4nums = [4,5,6,7,0] [1,2]    breakPos = 5nums = [4,5,6,7,0,1] [2]    breakPos = 6 

来看看分开之后的两部分，是不是至少有一部分是有序的？

那么我们是不是就能够在这有序的部分中去寻找target？

可以是可以，但是这样子的时间复杂度并非是二分查找的，而是要加上枚举breakPos位置的部分，合起来的时间复杂度就是，显然不太符合题目的要求。

想一想之前的过程，是不是有大量重复的计算量消耗在了不同的二分中呢？

比如我们在breakPos = 1,2,3,4的时候，如果target为4-7，是不是都要重复的去二分？

那能不能直接对这个breakPos进行二分呢？

可以！

考虑这样子的思路：

• 如果[lef,breakPos - 1]是有序的，而且nums[lef] <= target && target < nums[breakPos]，那么答案肯定是存在于[lef,breakPos - 1]，调整上界rig到breakPos - 1。
• 如果[breakPos，rig]是有序的，而且nums[breakPos] < target && target <= nums[rig]，那么答案肯定是存在于[breakPos,rig]中，调整下界lef到breakPos即可。

所以我们就可以直接在二分breakPos的时候，判断target是否存在了。

class Solution {

        int siz = nums.length;        int lef = 0,rig = siz - 1;        while(lef <= rig){            int mid = (lef + rig) >> 1;            if(nums[mid] == target)                return mid;            if(nums[0] <= nums[mid]){                if(nums[0] <= target && target < nums[mid])                    rig = mid - 1;                else                    lef = mid + 1;            }            else{                if(nums[mid] < target && target <= nums[siz - 1])                    lef = mid + 1;                else                    rig = mid - 1;            }        }        return -1;    }}

时间复杂度是，因为我们只需要二分breakPos，效率自然也不负所望。

总结

本题其实还是一个二分查找的模型，只是我们需要对二分之后两边的边界进行分类讨论，当一道题目是有序的或者说有着明确的大小关系，我们就可以向二分的方向去想，类似的还有像最小值最大化，或者最大值最小化这些情况，都是一些经典的二分思想的应用场景。

力扣链接：https://leetcode.cn/problems/search-in-rotated-sorted-array/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 710 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

            知识星球
            
    
    
        
        扫码加入星球
        查看更多优质内容
    
    https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412