点击这里，可以看到更多算法面试相关的内容~
描述主题升序数组的整数数组nums预先在未知的某个点旋转
例如，[0、1、2、4、5、6、7]在旋转时可能为[4、5、6、7、0、1、2]。
请在数组中搜索target。 如果数组中有此目标值，则返回其索引；否则返回-1。
示例1 :
输入： nums=[ 4，5，6，7，0，1，2 ]，target=0输出： 4个样本2 :
输入： nums=[ 4，5，6，7，0，1，2 ]，target=3输出：-1示例3 :
输入： nums=[1]，target=0输出：-1提示符：
1=nums.length=5000-10 ^4=nums [ I ]=10 ^4nums每个值只旋转-10^4=target=10^4。 示例1 :
输入： nums=[ 1，2，3 ]输出： [ 1，3，2 ]示例2 :
输入： nums=[ 3，2，1 ]输出： [ 1，2，3 ]示例3 :
输入： nums=[ 1，1，5 ]输出： [ 1，5，1 ]示例4 :
输入： nums=[1]输出： [1]提示：
1=nums.length=1000=nums[i]=100朴素的解法，但从有序排列中寻找某个数，我们的第一个反应应该是“两分钟”。
这个问题，本来是在有秩序的排列的某一点上旋转的，其实是把原本升序的排列分成了两部分。
首先找到旋转点idx，可以将idx的前后“二分”。
class解决方案{ public int search (int [ ] nums，int target ) { int n=nums.length； int idx=0； for(intI=0； i n - 1； I () if ) nums[I]nums[I1] ) { idx=i； 布雷克； }intans=find(nums，0，idx，target )； if(ans！=-1 )返回Ans； if(idx 1n ) ans=find(nums，idx1，n - 1，target )； 返回Ans； (intfind ) int[]nums，int l，int r，int target ) ) while(LR ) ) intmid=LR1； if(nums[mid]=target({r=mid； } else { l=mid 1； } } return nums[l]==target？ l : -1； }时间复杂度：首先扫描一次数组，找到idx。 复杂度为o(n ) o(n ) o(n ) n ) )，在idx前后进行二分搜索。 复杂度为o ) logn ) o ) (log{n} ) o ) logn )。 整体为o(n ) o(n ) o(n ) )
空间复杂性：
O ( 1 ) O(1) O(1) 二分解法不难发现，虽然在朴素解法中我们应用了「二分」查找。
但理论复杂度为 O ( n ) O(n) O(n)，实际复杂度也远达不到 O ( log n ) O(log{n}) O(logn)，执行效率取决于旋转点 idx 所在数组的下标位置。
那么我们如何实现 O ( log n ) O(log{n}) O(logn) 的解法呢？
这道题其实是要我们明确「二分」的本质是什么。
「二分」不是单纯指从有序数组中快速找某个数，这只是「二分」的一个应用。
「二分」的本质是两段性，并非单调性。只要一段满足某个性质，另外一段不满足某个性质，就可以用「二分」。
经过旋转的数组，显然前半段满足 >= nums[0]，而后半段不满足 >= nums[0]。我们可以以此作为依据，通过「二分」找到旋转点。
找到旋转点之后，再通过比较 target 和 nums[0] 的大小，确定 target 落在旋转点的左边还是右边。
然后再对目标区间进行「二分」，找 target。
class Solution { public int search(int[] nums, int target) { int n = nums.length; if (n == 0) return -1; if (n == 1) return nums[0] == target ? 0 : -1; // 第一次「二分」：找旋转点 // 由于第一段满足 >=nums[0]，第二段不满足 >=nums[0]，当使用 >=nums[0] 进行二分，二分出的是满足此性质的最后一个数 int l = 0, r = n - 1; while (l < r) { int mid = l + r + 1 >> 1; if (nums[mid] >= nums[0]) { l = mid; } else { r = mid - 1; } } // 通过和 nums[0] 进行比较，得知 target 是在旋转点的左边还是右边 if (target >= nums[0]) { l = 0; } else { l = l + 1; r = n - 1; } // 第二次「二分」：找 target while (l < r) { int mid = l + r + 1 >> 1; if (nums[mid] <= target) { l = mid; } else { r = mid - 1; } } return nums[r] == target ? r : -1; }}时间复杂度： O ( log n ) O(log{n}) O(logn)
空间复杂度： O ( 1 ) O(1) O(1)
最后这是我们「刷穿 LeetCode」系列文章的第 No.33 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
由于 LeetCode 的题目随着周赛 & 双周赛不断增加，为了方便我们统计进度，我们将按照系列起始时的总题数作为分母，完成的题目作为分子，进行进度计算。当前进度为 33/1916 。
为了方便各位同学能够电脑上进行调试和提交代码，我在 Github 建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode。在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和一些其他的优选题解。
#算法与数据结构
#LeetCode题解
#算法面试