旋转数组里找数，AI 用二分写了 3 版才写对，差距在哪

读完本文你将了解：旋转排序数组的二分查找核心思路 | AI 从暴力到最优的 3 版演进 | 面试中的关键边界处理

📋 题目

原题：给定一个经过旋转的升序数组 nums（如 [4,5,6,7,0,1,2]）和一个目标值 target，在 O(log n) 时间内找到 target 的下标，不存在则返回 -1。

💡 先问一个问题

如果你让 ChatGPT 写这道题，第一版代码会是怎样？

给你一个提示：它八成会先遍历一遍数组找到旋转点，然后再做二分查找。

这不算错——时间 O(n)，空间 O(1)，能 AC。但面试官要的是 O(log n)，你给 O(n)，这就有点尴尬了。

来看看 AI 怎么一步步自己纠正的。

🤖 第一版：AI 的朴素思路（找旋转点 + 二分）

defsearch(nums,target):# 找旋转点pivot=0foriinrange(1,len(nums)):ifnums[i]<nums[i-1]:pivot=ibreak# 在两个有序段中分别二分defbinary_search(left,right):whileleft<=right:mid=(left+right)//2ifnums[mid]==target:returnmidelifnums[mid]<target:left=mid+1else:right=mid-1return-1result=binary_search(0,pivot-1)ifresult!=-1:returnresultreturnbinary_search(pivot,len(nums)-1)

AI 的思路很"人类"——先把旋转点找到，数组切成两段有序区间，再各自二分。直觉上没毛病。

问题在哪？找旋转点用了 O(n) 的单次遍历。题目要求 O(log n)，这一步就超了。

复杂度：时间 O(n) + O(log n) → O(n)，空间 O(1)。

🧠 AI 的自我优化

把这段代码丢回给 AI，让它优化：

第 1 次优化：二分找旋转点

AI 意识到找旋转点也可以用二分——因为旋转后的数组，旋转点左边的元素都大于等于 nums[0]，旋转点右边的元素都小于 nums[0]。

deffind_pivot(nums):left,right=0,len(nums)-1whileleft<right:mid=(left+right)//2ifnums[mid]>nums[right]:left=mid+1else:right=midreturnleft

这一步把找旋转点降到了 O(log n)。整体变成O(log n) + O(log n) = O(log n)，已经达标了。

第 2 次优化：一步到位，不找旋转点直接二分

但 AI 接着发现：其实根本不需要先找旋转点——可以在一次二分搜索中同时处理旋转的情况。

关键发现：任意一个 mid 切下去，mid 的左右两边，必有一边是完全有序的。只需要判断 target 落在有序的那一半就行。

defsearch(nums,target):left,right=0,len(nums)-1whileleft<=right:mid=(left+right)//2ifnums[mid]==target:returnmid# 判断哪一半是有序的ifnums[left]<=nums[mid]:# 左半有序ifnums[left]<=target<nums[mid]:right=mid-1else:left=mid+1else:# 右半有序ifnums[mid]<target<=nums[right]:left=mid+1else:right=mid-1return-1

时间 O(log n)，空间 O(1)。完美满足题目要求。而且代码比两段式更短、更优雅。

☕ Java 实现（思路完全一致）

publicintsearch(int[]nums,inttarget){intleft=0,right=nums.length-1;while(left<=right){intmid=left+(right-left)/2;if(nums[mid]==target){returnmid;}if(nums[left]<=nums[mid]){// 左半有序if(nums[left]<=target&&target<nums[mid]){right=mid-1;}else{left=mid+1;}}else{// 右半有序if(nums[mid]<target&&target<=nums[right]){left=mid+1;}else{right=mid-1;}}}return-1;}

为什么要加 Java？CSDN 第一大用户群是 Java 开发者。用mid = left + (right - left) / 2防溢出，Java 面试官一定会揪。两版代码放一起，读者自己比，比我讲十句都有用。

下面是演进路线的可视化：

🔍 算法模式拆解：Modified Binary Search

这道题属于Modified Binary Search（变体二分搜索）模式。

经典二分的前提是「数组完全有序」。这道题的数组虽然被旋转了，但部分有序性还在——旋转点两侧各自保持升序，只是整体被截断了。

模式核心：每一次二分，至少能确定一半区间是有序的。利用「有序的一半」来判断 target 在哪。

识别这个模式的关键特征：

同类变体：

• LeetCode 81：允许重复元素（最坏退化为 O(n)）
• LeetCode 153：找旋转数组的最小值
• 山脉数组峰顶查找：先升后降的单峰结构

🏗️ 真实产品场景

这个模式在工程中出镜率挺高。

场景：版本回归检测

想象你维护一个 CI/CD Pipeline。每天晚上跑一次回归测试。某天突然发现测试挂了——但你不确定是最近哪次提交导致的。

你手上有最近 N 次构建的状态数组：[通过, 通过, 通过, 失败, 失败, 失败]（之前都通过，某次开始全失败）。

这就是一个旋转数组的变体——用 Modified Binary Search 可以在O(log N)次测试中找到第一个失败的构建，而不是逐个回溯。

另一个场景：循环日志缓冲区搜索。高性能系统的日志常常循环写入——最新日志在缓冲区中间某个位置，最旧的在它后面。要快速查到某个时间戳的日志，就把时间戳当 target，二分定位。

还有一个你可能每天在用但没意识到的例子：数据库 B+Tree 的范围查询优化。当查询范围跨越多页时，MySQL 的优化器会在旋转后的页链表中用类似二分的方式快速定位起始位置——本质就是这道题的思路。

✅ 面试官的点评

这道题是 Medium 里的"Hard 敲门砖"——面试官考这题，不是看你会不会写二分，而是看你能不能识别"部分有序"这个关键结构。

写到什么程度算"通过"：

• 能说清楚「每次二分，至少有一半有序」这个核心点
• 边界条件处理正确（nums[left] <= nums[mid]里的等号很关键）
• 时间 O(log n)

加分项：

• 用mid = left + (right - left) / 2而不是(left + right) / 2（防溢出）
• 能讨论 repeat 元素的退化情况（81 题）
• 能关联到真实工程场景

常见踩坑点：

• 忘了判断 mid 等于 target 时直接返回
• nums[left] <= nums[mid]写成<导致 [3,1] 这种两元素情况出错
• target 范围判断时漏掉等于号

📊 同类题推荐

来源说明：

• ✅ 已验证：LeetCode 33 官方题解 + AI 代码实测（Python 3 + Java 17 均可运行）
• 📄 文档：算法导论第 2 章「二分查找及其变体」