【每天学习一点算法 2026/03/27】搜索旋转排序数组

每天学习一点算法 2026/03/27题目搜索旋转排序数组整数数组 nums 按升序排列数组中的值 互不相同 。在传递给函数之前nums 在预先未知的某个下标 k0 k nums.length上进行了 向左旋转使数组变为 [nums[k], nums[k1], …, 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) 的算法解决此问题。旋转后的数组相当于被分割成了两片最先想到的肯定就是找到分割点也就是最大值的地方然后在两个区间进行二分查找。但是找到分割点只能顺序查找那么时间复杂度已经是O(n)了其实我们可以观察到随便取一个元素那他的两侧必定有一侧是有顺序的比如[4,5,6,7,0,1,2]中7 左侧是有序的 0 右侧是有序的我们可以根据这个规律来缩小二分查找的边界functionsearch(nums:number[],target:number):number{letleft0,rightnums.length-1// 左右边界初始为// 二分查找目标值while(leftright){constmidMath.floor((leftright)/2)// 找到目标值直接返回下标if(nums[mid]target){returnmid}if(nums[mid]nums[0]){// 左侧有序if(targetnums[mid]targetnums[0]){// 元素在左侧rightmid-1}else{// 元素在右侧leftmid1}}else{// 右侧有序if(targetnums[mid]targetnums[nums.length-1]){// 元素在右侧leftmid1}else{// 元素在左侧rightmid-1}}}return-1}题目来源力扣LeetCode