LeetCode hot100——33.搜索旋转排序数组：Java 二分模板与 O(log n) 实现-平芜编程栈

一句话说明核心方法

旋转只“切一刀”，所以[left, mid]和[mid, right]至少有一段是升序的。每次循环先判断哪段有序，再看 target 是否落在那段里——是就在该段内二分，不是就丢弃该段转向另一段。整体仍是 O(log n) 二分。

思路推导

题意转化：在一个局部有序（旋转了一次）的数组里找 target 下标，仍要求 O(log n)。

关键观察 1：旋转只切一刀，所以永远有一半是“干净”的有序段。把原始升序[0,1,2,4,5,6,7]在 k=3 处旋转，得到[4,5,6,7,0,1,2]：

切点(旋转点) ↓ 4 5 6 7 | 0 1 2 [有序递增段 ] [有序递增段]

两个段都还是升序，只是段间顺序“接错”了。在任意[left, right]子区间里取 mid，要么[left, mid]有序、要么[mid, right]有序（旋转点不可能同时落在两段内部）。这就是“在旋转数组上仍能二分的根本原因”。

关键观察 2：用nums[mid] >= nums[left]判哪段有序。左端点nums[left]是这一段的“地基”：

若nums[mid] >= nums[left]，说明[left, mid]这段没跨越切点，整段升序；
否则说明切点在[left, mid]内部，[mid, right]才是干净的升序段。

注意用>=而非>——因为旋转点处nums[left]可能等于nums[mid]（虽然本题约束无重复，但写法要养成左闭右闭区间下“等于归左”的习惯）。

**关键观察 3：在有序段里直接用 target 与两端点的关系做“跳转”。**比如判断出左半[left, mid]有序：

若target ∈ [nums[left], nums[mid])→ target 在左半段内，下一轮往左搜（right = mid - 1）；
否则 target 要么在右半段里、要么根本不存在，下一轮直接跳到右半（left = mid + 1）。

对右半有序段做完全对称的判断。一句“target落点判断”就把“在这一段搜 / 丢掉这一段”的决策表达完了。

对比另一种思路：还有一种更直白的两步法——先二找出旋转点 k（数组最小值的下标），再判断 target 在[k, n-1]还是[0, k-1]，最后在对应段做标准二分。代码会多一个找最小值的循环，但逻辑分支更少。一份循环直接定位vs三段式两步法，各有适用场景：前者面试展现“压缩分支”能力，后者更接近“从已知工具拼出来”的本能。本题里两种写法都是 O(log n)。

二分过程示意(nums = [4,5,6,7,0,1,2],target = 0)

初始: left = 0, right = 6 0 1 2 3 4 5 64 5 6 7 0 1 2 L M R mid = 3, nums[3] = 7 判断: nums[3]=7 >= nums[0]=4 → 左半 [0..3] 有序 [4,5,6,7] target=0 落在 [4,7)?4 ≤ 0 不成立 → target 不在左半 → left = 4 0 1 2 3 4 5 6 4 5 6 7 0 1 2 L M R mid = 5, nums[5] = 1 判断: nums[5]=1 >= nums[4]=0 → 左半 [4..5] 有序 [0,1] ←★关键:切点滑到 mid 左边了 target=0 落在 [0,1)? 0 ≤ 0 且0 < 1 成立 → 在左半 → right = 4 0 1 2 3 4 5 6 4 5 6 7 0 1 2 L,R mid = 4, nums[4] = 0 M nums[4] = 0 == target → return 4 ✓

注意第2 轮：mid=5 上的nums[5]=1 >= nums[4]=0仍然成立，于是左半[4,5] = [0,1]也被判为有序。只要 mid 不跨过切点，左半段的内部顺序就是对的——这正是“至少一段有序”不变量的现场演示。

Java 完整代码

java

class Solution { 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[mid] >= nums[left]) { // 左半 [left, mid] 有序 // ② target落在左半有序段里 →收左;否则切到右半 if (target >= nums[left] && target < nums[mid]) { right = mid - 1; } else { left = mid + 1; } } else { // 右半 [mid, right] 有序 // ③ 对称判断 if (target > nums[mid] && target <= nums[right]) { left = mid + 1; } else { right = mid - 1; } } } return -1; // 区间空,找不到 } }

关键代码逐行解释

if (nums[mid] == target) return mid——本题数组无重复（题目明确保证），命中即唯一，提前返回既正确又省轮次。如果迁移到 LeetCode 81（允许重复），就不能提前 return——重复元素下“== target” 会落在旋转点附近提前结束，留到结尾判定才稳。
nums[mid] >= nums[left]——左半有序的判定式。原理：左半[left, mid]整体升序，当且仅当它的两端nums[left] ≤ nums[mid]，即nums[mid] >= nums[left]。等号成立的唯一情况是 mid == left（区间长度为 1），此时单元素区间天然有序，写>=把这种情况也正确归入“左半有序”。如果改用>，会出现 mid == left 时漏判、跳到 else 分支的隐患。
target >= nums[left] && target < nums[mid]——左半有序段的“落点判断”。注意右端用< nums[mid]而不是<=,因为nums[mid] == target已在前面 return,这里 mid 上的值一定不是 target,所以左半段的 target 范围是“含左端、不含右端”的左闭右开。反过来右半有序段用target > nums[mid] && target <= nums[right],“不含左、含右”。两段端点严格性相反，正是 mid 这个位置被排除两次的体现。
else { left = mid + 1; }(左半有序但 target 不在内)——直接丢弃整个左半。target 要么在右半、要么不存在，下一轮往右搜。这步“丢半段”的力度和标准二分一样，复杂度仍是 O(log n) 的保证来源。
右半有序的对称分支——target > nums[mid] && target <= nums[right]的语义镜像左半。两边边界严格性刻意相反（左半>= left && < mid、右半> mid && <= right），保证 mid 这个位置不归任何一边（因为它已经在前一行被排除了）。
return -1——区间被切到空（left > right）还没命中，说明数组里没有 target。这点其实在循环内已被覆盖（每轮必丢一半），但作为出口必须显式写，否则编译器报警告、判题也认。

时间、空间复杂度

时间复杂度：O(log n)
- 每轮循环至少把[left, right]区间严格缩短一半（要么left = mid + 1、要么right = mid - 1，mid 本身被排除），从 n 收敛到 1 最多 ⌈log₂ n⌉ 轮。本题数组无重复，最坏情况也严格 O(log n)；如果迁移到含重复的 81，最坏退化为 O(n)（旋转点附近nums[mid] == nums[left]时无法判断哪半有序，必须线性收一格）。
空间复杂度：O(1)
- 只用 left / right / mid 三个变量，无递归无辅助结构。

易错点

没判“哪半有序”直接套普通二分：把旋转数组当普通升序数组二分，target落在“切点后的降序段”时会被误丢，复杂度还可能错。判有序段是旋转二分的“前置动作”，省略就错。
有序段判定写成>而不是>=：mid == left 时（区间只剩两个元素）左半是单元素数组，本应有序，写nums[mid] > nums[left]会因为0 个元素差异或单元素相等被错归为“右半有序”，分支逻辑跑偏。
target 落点边界写错：target <= nums[mid]在左半有序段里会出现 mid 上恰好等于 target 的情况，被前面nums[mid] == target排除后又错误归入“落在左半”，多绕一轮还可能正确，但严谨性扣分。左闭右开、右闭右开的严格性要和分支对齐。
没考虑 mid == left 的退化：n = 2 时 mid == left 是常态，判有序段 +落点要能正确处理单元素子区间，否则[3,1]、target=1这种小输入会卡死或漏判。
数组未旋转时还要走完整套逻辑：未旋转就是“切点在0”这种特殊情形，代码也应正常工作——你的写法天然兼容（nums[mid] >= nums[left]永远成立，整个区间判为左半有序，再走普通二分路径），不必另写分支。

可复用模板

抽出“先判有序段、再判落点”的母版，覆盖一切“部分有序数组”的搜索题：

java

class Solution { public int search(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) return mid; if (nums[mid] >= nums[left]) { // ① 左半有序 if (target >= nums[left] && target < nums[mid]) { // ② 落在左半 right = mid - 1; } else { left = mid + 1; // ③ 跳到右半 } } else { // 右半有序(与①互补) if (target > nums[mid] && target <= nums[right]) { // ④ 落在右半 left = mid + 1; } else { right = mid - 1; // 跳到左半 } } } return -1; } }

变体提示：

找最小值 / 旋转点(LeetCode 153) → 把target换成“nums[mid]与nums[right]的比较”,不查存在性,只维护“最小值在右半还是左半”的不变量。
允许重复(LeetCode 81) →nums[mid] == nums[left]时无法判有序,把left++收缩一格，最坏退化为 O(n)。
找旋转后数组的特定 target范围(如“找出 target 第一次出现和最后一次出现”) → 二分两遍，每遍用相同的“判有序段 + 判落点”逻辑，分支条件取target >= nums[mid]/target <= nums[mid]即可。

相似题及区别

LeetCode 81 搜索旋转排序数组 II：本题的“含重复”版。旋转点附近nums[mid] == nums[left]时无法判定哪半有序，需要left++收缩一格，最坏 O(n)；本题因无重复，严格 O(log n)。这道题是检验“真懂二分 vs 只会套模板”的最佳陷阱题。
LeetCode 153 寻找旋转排序数组中的最小值：把“找 target”换成“找切点”，结构同源——同样判有序段（这次是nums[mid] > nums[right]），同样收半段，但不需要 target 落点判断。配合本题构成“旋转数组双子星”。
LeetCode 74 搜索二维矩阵：上一题。本题是“一维局部有序”，上一题是“二维全局有序（虚拟展开后）”，复杂度都是 O(log n) 但有序性的来源完全不同。本题是“旋转切一刀所以仍可二分”，上一题是“矩阵拼接成一条线所以天然二分”，对比阅读能加深对“何种有序才能二分”的理解。
LeetCode 34 在排序数组中查找元素的第一个和最后一个位置：把“找边界”的思路迁移过来——旋转数组里也能找 target 的最早 / 最晚位置，方法就是用本题模板跑两遍，分别把==归入左半或右半，正好对应 lower / upper bound 的等号方向。