LeetCode 33. 搜索旋转排序数组：O(log n)二分查找

在LeetCode中等难度题目中「搜索旋转排序数组」是一道经典的二分查找变形题。它的核心考点的是对“旋转数组”特性的理解以及如何在非完全升序的数组中依然保持二分查找O(log n)的时间复杂度。今天就来一步步拆解这道题从题目分析到代码实现再到细节注意点帮你彻底搞懂它。一、题目解读什么是旋转排序数组题目给出的前提很明确原数组是升序排列的且所有元素互不相同这一点很关键避免了重复元素带来的判断干扰数组在某个未知下标k处「向左旋转」旋转后数组变成 [nums[k], nums[k1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]给定旋转后的数组nums和目标值target要求找到target的下标找不到则返回-1且必须满足O(log n)时间复杂度。举个例子原数组 [0,1,2,4,5,6,7]在k3处向左旋转后得到 [4,5,6,7,0,1,2]。如果target0返回下标4如果target3返回-1。这里的核心矛盾是数组不再是完全升序但又保留了“部分升序”的特性——旋转后数组会被分成两个升序子数组比如例子中的 [4,5,6,7] 和 [0,1,2]。而二分查找的核心是“通过中间值缩小查找范围”所以我们的思路就是利用这种“部分升序”判断target落在哪个升序区间进而调整双指针。二、核心思路二分查找的变形应用常规二分查找适用于完全升序数组通过mid值与target的大小对比直接调整左右指针。但旋转数组有两个升序区间所以我们需要先判断「mid所在的区间是否是升序区间」再判断target是否在该区间内从而确定指针移动方向。具体步骤拆解初始化双指针l0左边界、rn-1右边界n为数组长度循环条件l ≤ r当l超过r时说明查找范围为空未找到target计算mid Math.floor((l r) / 2)注意TS/JS中除法会返回浮点数需手动取整若nums[mid] target直接返回mid找到目标值判断mid所在的区间是否为升序情况1nums[0] ≤ nums[mid] → mid左侧l到mid是升序区间情况2nums[0] nums[mid] → mid右侧mid到r是升序区间根据升序区间判断target是否在该区间内调整指针情况1左侧升序若target在[nums[0], nums[mid])之间 → 缩小范围到左侧rmid-1否则缩小到右侧lmid1情况2右侧升序若target在(nums[mid], nums[n-1]]之间 → 缩小范围到右侧lmid1否则缩小到左侧rmid-1循环结束后仍未找到返回-1。三、完整代码实现TypeScript结合上述思路给出完整的TypeScript代码关键步骤已添加注释方便理解functionsearch(nums:number[],target:number):number{constnnums.length;// 边界处理数组为空直接返回-1if(n0){return-1;}// 边界处理数组只有一个元素直接判断是否等于targetif(n1){returnnums[0]target?0:-1;}// 初始化双指针左指针l右指针rletl0,rn-1;// 二分查找循环当左指针不大于右指针时继续查找while(lr){// 计算中间下标mid手动取整避免浮点数constmidMath.floor((lr)/2);// 找到目标值直接返回下标if(nums[mid]target){returnmid;}// 情况1mid左侧是升序区间nums[0] nums[mid]if(nums[0]nums[mid]){// 判断target是否在左侧升序区间内nums[0] target nums[mid]if(nums[0]targettargetnums[mid]){// 缩小范围到左侧右指针左移rmid-1;}else{// 缩小范围到右侧左指针右移lmid1;}}else{// 情况2mid右侧是升序区间nums[0] nums[mid]// 判断target是否在右侧升序区间内nums[mid] target nums[n-1]if(nums[mid]targettargetnums[n-1]){// 缩小范围到右侧左指针右移lmid1;}else{// 缩小范围到左侧右指针左移rmid-1;}}}// 循环结束未找到目标值返回-1return-1;}四、关键细节与易错点这道题的代码不算复杂但细节处理不到位很容易出错尤其是以下3个点1. 边界条件处理必须先处理数组为空n0和数组只有一个元素n1的情况。如果忽略这两个边界当数组长度为0时会出现指针异常长度为1时会进入循环做无用功影响效率。2. mid的计算方式在TypeScript/JavaScript中(l r) / 2 会返回浮点数比如l0、r1时结果是0.5所以必须用Math.floor()取整否则mid会是小数导致数组下标报错。补充也可以用 (l r) 1 进行位运算取整效果等同于Math.floor((l r)/2)但要注意避免溢出本题中数组长度不会过大两种方式均可。3. 区间判断的等号问题这是最容易出错的地方比如左侧升序区间判断时用 nums[0] ≤ nums[mid]包含等于因为mid可能就是0下标此时左侧只有一个元素也是升序target在左侧区间的判断的是 nums[0] ≤ target target nums[mid]target不能等于nums[mid]因为前面已经判断过nums[mid] ! target右侧升序区间判断时target的范围是 nums[mid] target target ≤ nums[n-1]同理target不能等于nums[mid]。如果等号位置写错会导致指针调整错误进而错过目标值或者进入死循环。五、复杂度分析与题目延伸1. 时间复杂度整个算法采用二分查找每次循环都会将查找范围缩小一半所以时间复杂度是 O(log n)完全满足题目要求。2. 空间复杂度算法只使用了常数个变量l、r、mid、n没有使用额外的空间空间复杂度是 O(1)。3. 题目延伸这道题的变形题是「搜索旋转排序数组II」区别在于数组元素可以重复。此时nums[0] ≤ nums[mid] 无法直接判断左侧是升序区间比如 [1,0,1,1,1]需要先处理重复元素比如当nums[l] nums[mid]时l感兴趣的可以后续深入研究。六、总结「搜索旋转排序数组」的核心是“利用旋转数组的部分升序特性改造二分查找”。解题的关键在于判断mid所在的升序区间根据target是否在该升序区间调整双指针注意边界条件和等号的处理。这道题虽然是中等难度但只要掌握了二分查找的核心思想再结合旋转数组的特性就能轻松破解。建议大家多动手调试代码尝试不同的测试用例比如旋转点在开头、结尾、中间的情况加深对算法的理解。