搜索旋转排序数组这道题，几乎每个刷力扣的人都绕不过去。我第一次做的时候，第一反应是：都旋转过了，还怎么二分？后来才发现，旋转恰恰是这道题的题眼——它把数组切成了两段，每段内部依然有序。如果你正准备面试、在刷力扣热题100，或者想在二分查找这个考点上建立自己的解题模板，这题值得放到进度单最前面。网上题库版本很多，有标成第66题的，也有写第33题的，反正都是同一个 Search in Rotated Sorted Array，力扣官网直接用题面就能搜到。今天我把完整推导、三种语言实现和相关变种题一起整理出来。
搜索旋转排序数组的表面问题是"在一个经过旋转的升序数组里找目标值"，真正考的是你对二分查找边界条件的理解。暴力遍历当然能过，但面试官想听的是 O(log n) 的解法。接下来我会从旋转数组的结构讲起，逐步拆到代码边界，再延伸到几道高频变种题。
1. 旋转数组的结构：为什么一分为二后仍有有序段
1.1 一次旋转动作究竟改变了什么
先看一个最朴素的例子：原数组是[0,1,2,3,4,5,6,7]，在索引 4 的位置旋转，就得到[4,5,6,7,0,1,2,3]。这种操作在很多算法书里叫"循环右移"，你可以理解为把末尾的一段搬到开头，也可以理解为把数组从某个切点断开后交换两部分的位置。
旋转后数组看起来"乱"了，但它有两个关键特征：
- 数组被切成了两段，每一段内部仍然保持严格递增。
- 第一段的所有元素都大于第二段的所有元素，前提是确实发生过旋转且数组原本严格升序。
举个例子就清楚：[4,5,6,7,0,1,2,3]中，[4,5,6,7]是一段，[0,1,2,3]是另一段。4 到 7 递增，0 到 3 也递增，但 7 到 0 是断的。这个断点就是旋转点，也叫最小值所在的位置。
判断数组到底有没有旋转，可以直接比较nums[0]和nums[nums.length-1]。如果nums[0] > nums[last]，说明旋转了；如果nums[0] < nums[last]，说明数组整体没有旋转，本来就是普通升序。这个细节后面写代码时很有用，尤其是处理"无旋转"的测试用例。
1.2 普通二分为什么在这里失效
普通二分查找有一个前提：整个数组单调有序。这样我们可以通过比较nums[mid]和target的大小，直接决定继续搜索左半部分还是右半部分。但旋转数组不是全局有序的，nums[mid]比target大时，目标既可能在 mid 左边，也可能在 mid 右边。
我习惯用一个路况类比：一条公路中间某处塌方了，路面被分成两段，每段内部的路标仍然连续，但从断点处无法直达。你在其中一段上做判断，不能只盯着当前路标，得先搞清楚自己站在哪一段，以及目标在哪一段。放到数组里就是：mid左边和右边，必然有一边是完整有序的，我们要先判断出哪边有序，再决定去留。
1.3 两个有序段的使用策略
假设搜索区间是[left, right]，中间位置是mid。核心判断只有两句：
- 如果
nums[left] <= nums[mid]，说明左半段[left, mid]是完整递增的。此时先看target是否落在[nums[left], nums[mid])范围内。落在左段就去左半段找，否则去右半段。 - 如果
nums[left] > nums[mid]，说明旋转点切在了左半段，那么右半段[mid, right]才是完整递增的。此时看target是否落在(nums[mid], nums[right]]范围内。落在右段就去右半段找，否则去左半段。
为什么要先判断哪段有序？因为有序区间内的判断是可靠的：目标值如果落在有序区间的端点之间，说明它一定可以在这段里用普通二分的思路继续收缩；如果不在这个区间，那它只可能出现在另一段。每次循环都能把搜索范围缩掉一半，整体就是 O(log n)。
2. 二分查找的判定细节：为什么判断左段有序用 <= 而不是 <
2.1 mid 落在哪一段是分水岭
我用两个具体例子演示一下判定过程。
例子 A：nums = [4,5,6,7,0,1,2], target = 1，初始left=0, right=6, mid=3。此时nums[mid] = 7，nums[left] = 4，满足4 <= 7，所以左半段有序。再看target=1是否落在[4,7)里？显然不在，于是left = mid + 1 = 4。下一轮mid=5, nums[mid]=1，命中。
例子 B：nums = [5,6,7,0,1,2,4], target = 6，初始left=0, right=6, mid=3。此时nums[mid] = 0，nums[left] = 5，不满足5 <= 0，所以左半段不是完整有序。那么右半段[3,6]也就是[0,1,2,4]是完整递增的。现在检查target=6是否落在(0,4]？不在，于是right=mid-1=2。下一轮在[5,6,7]里找，很快命中。
这两个例子说明：nums[left] <= nums[mid]这个判断，本质上是在回答"mid 是否和 left 位于同一个递增段里"。如果是，左段有序；如果不是，说明 mid 已经跑到了第二段，真正的旋转点在 left 和 mid 之间。
2.2 边界相等的情况：两个元素时的特殊处理
当区间缩小到只剩两个元素时，比如nums=[1,3]，left=0, right=1, mid=0，此时nums[left] == nums[mid]，<=成立，程序会走进"左段有序"分支。因为左段只有一个元素[1]，它确实是有序的，这个结果没问题。
但如果用<来判断，nums[left] < nums[mid]变成 false，程序会错误地走进"右段有序"分支。虽然在一些特定写法里也能补救，但很容易把思路绕进去。所以我个人强烈建议：判断左段有序的条件写成nums[left] <= nums[mid]，把等于的情况归为左段有序。等于是"单个元素也算一段有序序列"，逻辑上更干净。
2.3 别把 target 的等于号写丢
再看两条区间判断条件的细节：
# 左段有序时 if nums[left] <= target < nums[mid]: right = mid - 1 else: left = mid + 1 # 右段有序时 if nums[mid] < target <= nums[right]: left = mid + 1 else: right = mid - 1为什么左段有序分支里，target和nums[mid]比较时是严格小于？因为在进入分支前，我们已经单独判断过：
if nums[mid] == target: return mid既然nums[mid]已经排除了等于 target 的情况，那么在后续判断里只需要考虑严格小于或严格大于。如果你一样都写成了<=，处理起来也不会有大错，但逻辑会变得含糊，调试时很难一眼看出问题。
右段有序分支同理：nums[mid] < target是严格大于，因为等于的情况已经被前置判断拦截了。这里我踩过不止一次：把<=写错位置，导致返回结果差一位。后来养成了习惯，写完整段代码后，先拿[3,1]、[1,3]这种两个元素的极端用例跑一遍，再提交。
3. 三种语言实现：从逻辑到代码的完整映射
3.1 Python 版本：最直观的写法
def search(nums, target): left, right = 0, len(nums) - 1 while left <= right: mid = left + (right - left) // 2 if nums[mid] == target: return mid # 左半段有序 if nums[left] <= nums[mid]: if nums[left] <= target < nums[mid]: right = mid - 1 else: left = mid + 1 # 右半段有序 else: if nums[mid] < target <= nums[right]: left = mid + 1 else: right = mid - 1 return -1这段代码看起来短，但每一行都有讲究。mid = left + (right - left) // 2不使用(left + right) // 2，唯一原因是让相同逻辑迁移到 Java、C++ 时也能避免整型溢出。Python 的 int 没有溢出问题，写成这样只是为了统一习惯。
测试用例可以这样验证：
输入: nums = [4,5,6,7,0,1,2], target = 0 过程: mid 依次检查 7、0，最终返回 4 输入: nums = [4,5,6,7,0,1,2], target = 3 过程: 所有元素检查完毕后退出循环，返回 -1 输入: nums = [1], target = 0 过程: left=0, right=0, mid=0, nums[0]!=0, 返回 -13.2 Java 版本：注意溢出和位运算
public int search(int[] nums, int target) { int left = 0; int right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } 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 里最容易翻车的点是left + right溢出。当nums.length接近Integer.MAX_VALUE时，left + right可能超过 int 范围。所以计算 mid 必须写成left + (right - left) / 2。我见过不少人在本地小数组上测试正常，一提交就报错，多半就是这里溢出了。
还有一点：Java 条件里不能像 Python 那样写链式比较，必须把nums[left] <= target && target < nums[mid]拆开写。两种语言混着刷的人，经常在这个地方手滑漏了后半句。
3.3 C++ 版本：和 STL 风格保持一致
class Solution { public: int search(vector<int>& nums, int target) { int left = 0; int right = nums.size() - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } 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; } };C++ 写法和 Java 几乎一致，唯一要留意的是nums.size()返回的是size_t类型，无符号数。如果直接把它赋给 int，在数组为空时nums.size() - 1会变成一个巨大值，导致越界访问。所以要么先判空，要么像上面这样用int right = nums.size() - 1;并在进入前确认nums非空。
3.4 时空复杂度与典型用例对比
| 语言 | 核心写法 | 时间复杂度 | 空间复杂度 | 注意事项 |
|---|---|---|---|---|
| Python | 链式比较清晰 | O(log n) | O(1) | 无溢出风险，但需注意缩进 |
| Java | 拆开 && 比较 | O(log n) | O(1) | 防止 left+right 溢出 |
| C++ | 拆开 && 比较 | O(log n) | O(1) | 防止 size_t 类型转换问题 |
补一组最常见的边界用例，写完后务必自测：
[1,3] 找 3 -> 1 [3,1] 找 1 -> 1 [1,2,3,4] 找 2 -> 1 （无旋转的情况） [1,2,3,4] 找 5 -> -1 [1] 找 0 -> -1无旋转数组是很容易被忽略的输入。因为nums[left] <= nums[mid]全程成立，每个循环都会走进左段有序分支，左段就是整个数组，判断逻辑会逐渐退化成普通二分查找，所以不会出错。这也是模板设计时隐含的一个优点。
4. 高频变种：找最小值、允许重复、旋转点定位
4.1 找旋转数组的最小值
力扣原题里搜索旋转排序数组是 33 题，找旋转数组的最小值在力扣是 153 题，面试中经常成对出现。思路其实更简单：我们不需要某个 target，只需要不断缩小区间，让 left 和 right 最终指向最小值。
def findMin(nums): left, right = 0, len(nums) - 1 while left < right: mid = left + (right - left) // 2 if nums[mid] > nums[right]: left = mid + 1 else: right = mid return nums[left]这个代码的内部逻辑是：如果nums[mid] > nums[right]，说明 mid 在左段，最小值在右段，所以移动left = mid + 1；否则 mid 可能在右段或者右段完全有序，最小值在 mid 或 mid 左边，就移动right = mid。
注意这里用的是left < right，不是left <= right。因为找最小值最终区间会收敛到left == right，如果再进入循环，可能出现死循环。和左侧搜索 target 的模板不同，找最小值天然适合左闭右开式收缩。
4.2 允许重复元素：原题从 33 变 81
很多场景下数组并不严格递增，可能有重复值，比如[2,2,2,0,2,2]。这种情况下，nums[left] <= nums[mid]虽然仍成立，但无法区分 mid 到底在左段还是右段，因为中间出现了大量相等元素，旋转点被"藏"起来了。
处理方式比较粗暴但有效：当nums[left] == nums[mid] && nums[mid] == nums[right]时，我们无法判断哪侧有序，只能把 left 和 right 同时向中间收缩一步，比如left++和right--，然后再继续二分。这样会破坏 O(log n) 的严格保证，最坏情况变成 O(n)，但这也是唯一能保证正确性的通用办法。
def searchWithDuplicates(nums, target): left, right = 0, len(nums) - 1 while left <= right: mid = left + (right - left) // 2 if nums[mid] == target: return True if nums[left] == nums[mid] == nums[right]: left += 1 right -= 1 elif nums[left] <= nums[mid]: if nums[left] <= target < nums[mid]: right = mid - 1 else: left = mid + 1 else: if nums[mid] < target <= nums[right]: left = mid + 1 else: right = mid - 1 return False这个变种在力扣是 81 题，面试时如果先问你 33 题，大概率会紧跟一句"如果有重复元素该怎么改"，所以最好提前把这一版也准备好。
4.3 找旋转点：用二分定位断层位置
严格意义上的旋转点，就是nums[i] > nums[i+1]的那个位置。最简单的方法是线性扫描，但既然题目强调 O(log n)，我们还是用二分找最小值的位置，最小值所在下标就是旋转点。
举个例子：[4,5,6,7,0,1,2]中最小值是 0，下标为 4，那么旋转点就在下标 4。旋转点往前的元素[4,5,6,7]是原数组尾部，旋转点往后的元素[0,1,2]是原数组头部。一旦找到了旋转点，整个数组的"真相"就还原了。
实际项目里这种问题也不少见。我做过日志采集系统的时间戳数组、监控指标的采样序列，因为服务重启或数据回填，经常出现"有序但分段"的情况。这时候通用的查找逻辑基本就是在数组上做旋转点定位加区间二分。
4.4 变种题对比：一份模板解决四道题
| 题目场景 | 循环条件 | 核心判断 | 返回结果 | 最坏复杂度 |
|---|---|---|---|---|
| 搜索目标值(无重复) | left <= right | nums[left] <= nums[mid] | 目标下标/-1 | O(log n) |
| 搜索目标值(有重复) | left <= right | 相等时 left++/right-- | 是否存在 | O(n) |
| 找最小值(无重复) | left < right | nums[mid] > nums[right] | nums[left] | O(log n) |
| 找旋转点 | left < right | 同上，最终下标即旋转点 | 下标 | O(log n) |
可以把这个表格当成刷题自查清单。今天这篇博文主要解决第一行，后三行是很好的延伸练习。
5. 刷这题踩过的坑与落地模板
5.1 循环条件用 left <= right 还是 left < right
很多初学者在这道题上迷茫，不是因为判断逻辑不会写，而是分不清循环条件。
我的经验是分场景：
- 要查找某个确切值，用
while (left <= right)。循环结束后 left > right，说明没找到。 - 要查找最小值、旋转点，用
while (left < right)。循环结束后 left 和 right 重合，这个位置就是答案。
如果把查找 target 的代码改成left < right，那么循环提前结束，最后还要补一句：
if nums[left] == target: return left有些选手习惯这种写法，也不是不行。但为了减少思考负担，我建议查找值就用left <= right，找位置就用left < right，形成肌肉记忆。
5.2 最前面判断 nums[mid] == target
我之前犯过一个错误：不在循环开头判等，而是把等于情况混进区间条件里。比如if nums[left] <= target <= nums[mid]时移动 right，否则移动 left，最后在循环外面返回。这样写初看也没问题，但遇到目标元素恰好就是 nums[mid] 时，边界处理会变得非常绕：到底是走 left 分支还是 right 分支？你可以推导出来，但很容易在面试白板上卡壳。
正确做法是把if nums[mid] == target放在最开头，后续区间判断里只保留严格的<和>。这样每一步的逻辑都非常纯粹：先回答"中位数是不是答案"，再回答"该去哪半边找"。
5.3 "无旋转"输入别翻车
有些测试用例刻意不给旋转数组，比如[1,2,3,4,5]。如果模板里有一句判断"如果nums[left] < nums[right]直接普通二分"当然可以，但即使不写也不会出错，因为我们前面的nums[left] <= nums[mid]分支始终成立，每次都把区间按普通二分的方式收缩。它不会漏掉任何情况。
但要注意：不能在代码里写"如果nums[0] < nums[last]就直接返回 -1"，因为 target 可能是正常存在于数组中的。我见过有同学试图用旋转标志提前过滤，结果把无旋转但 target 存在的用例给过滤掉了。
5.4 我最终固定下来的手写模板
经过多次踩坑后，我刷搜索旋转排序数组类题目时，固定使用下面这套思路，基本五分钟能写完：
1. 初始化 left=0, right=n-1。 2. 循环 left <= right。 3. mid = left + (right-left)//2。 4. if nums[mid] == target，返回 mid。 5. if nums[left] <= nums[mid]： 左段有序；target 在 [nums[left], nums[mid]) 就收缩 right，否则收缩 left。 6. else： 右段有序；target 在 (nums[mid], nums[right]] 就收缩 left，否则收缩 right。 7. 循环结束返回 -1。这套模板的好处是，所有等于号的位置都是固定的：mid 与 target 的比较在开头，左段有序判断用<=，左段区间判断用<= target < mid，右段区间判断用mid < target <=。只要把这四个位置记住，代码就不会出现边界错误。
再分享一个调试技巧。如果本地测试出现死循环，通常问题出在两处：一是该用left < right却用了left <= right，二是mid = left + (right - left) // 2写成了向上取整。遇到这种情况，不要直接改循环条件，先在纸上画一个长度为 4 或 5 的数组，手动算一轮 left、mid、right 的变化，很快就能定位是哪个分支没走对。
搜旋转排序数组这道题，看起来只是一道二分查找，但它把"有序性判断""边界处理""退化场景"三个知识点全考了一遍。我后来刷力扣热题100，凡是二分相关题目，几乎都拿它当基准模板。面试前如果时间紧，我只复习两题：普通二分查找和搜索旋转排序数组，因为由后者延伸出去的最小值、重复值、旋转点等变种，都是同一套思维方式。
