 实现)
一句话说明核心方法旋转只“切一刀”所以[left, mid]和[mid, right]至少有一段是升序的。每次循环先判断哪段有序再看 target 是否落在那段里——是就在该段内二分不是就丢弃该段转向另一段。整体仍是 O(log n) 二分。思路推导题意转化在一个局部有序旋转了一次的数组里找 target 下标仍要求 O(log n)。关键观察 1旋转只切一刀所以永远有一半是“干净”的有序段。把原始升序[0,1,2,4,5,6,7]在 k3 处旋转得到[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] target0 落在 [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 左边了 target0 落在 [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 轮mid5 上的nums[5]1 nums[4]0仍然成立于是左半[4,5] [0,1]也被判为有序。只要 mid 不跨过切点左半段的内部顺序就是对的——这正是“至少一段有序”不变量的现场演示。Java 完整代码javaclass 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 - 1mid 本身被排除从 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]、target1这种小输入会卡死或漏判。数组未旋转时还要走完整套逻辑未旋转就是“切点在0”这种特殊情形代码也应正常工作——你的写法天然兼容nums[mid] nums[left]永远成立整个区间判为左半有序再走普通二分路径不必另写分支。可复用模板抽出“先判有序段、再判落点”的母版覆盖一切“部分有序数组”的搜索题javaclass 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 的等号方向。
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]在 k3 处旋转得到[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] target0 落在 [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 左边了 target0 落在 [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 轮mid5 上的nums[5]1 nums[4]0仍然成立于是左半[4,5] [0,1]也被判为有序。只要 mid 不跨过切点左半段的内部顺序就是对的——这正是“至少一段有序”不变量的现场演示。Java 完整代码javaclass 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 - 1mid 本身被排除从 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]、target1这种小输入会卡死或漏判。数组未旋转时还要走完整套逻辑未旋转就是“切点在0”这种特殊情形代码也应正常工作——你的写法天然兼容nums[mid] nums[left]永远成立整个区间判为左半有序再走普通二分路径不必另写分支。可复用模板抽出“先判有序段、再判落点”的母版覆盖一切“部分有序数组”的搜索题javaclass 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 的等号方向。