旋转升序数组上的二分搜索：为何“哪边有序“成为关键决策

这题的本质还是二分搜索，只是先用"哪一半有序"来锁定一个可信的有序区间，然后在这个区间里用普通二分的逻辑排除另一半。整套思路同时适用于普通升序数组和旋转升序数组，可以当成一个更通用的二分模板来记。algo+1​

题目与现象：为什么"整体不升序"还能二分？

题目给的是一个原本严格升序的数组，整体向左旋转了一段，比如：

• 原数组：[0,1,2,4,5,6,7]
• 旋转后：[4,5,6,7,0,1,2]。

旋转之后，有两条重要性质：notes.suhaib+1​

1. 数组被切成"前后两段各自升序"的形状，只在某一个位置出现"从大跳到小"的转折点。
2. 不管在数组哪里取一个 mid，把当前区间 [left, right] 切成两半，总有一半是完全升序的连续区间。

这就是整个解法的支点：虽然整体不升序，但"每一步里，总有一半是升序的"，在这半边上就可以像普通二分那样思考。algo+1​

关键洞见：如何判断"哪一半有序"？

假设当前在区间 [left, right] 上二分，取中点 mid。想判断左半 [left, mid] 是否有序：notes.suhaib+1​

• 如果左半里存在旋转点，即存在那次"从大跳小"的地方，那么一定有nums[left] > nums[mid]：
  • 直觉上：left 还在"尾部大段"，mid 已经绕到"头部小段"，所以左端值比中点值大。
• 反过来说，如果观测到nums[left] <= nums[mid]，就说明在 [left, mid] 这一段里没有那次"从大跳小"，也就没有旋转点，这整段只能是原数组中的某一段连续片段，因此是严格升序的。

结论就是那句经典判定：stackoverflow+2​

• 若nums[left] <= nums[mid]：左半 [left, mid] 有序；
• 否则右半 [mid, right] 有序（因为整个结构最多只有一个转折点，且两边至少有一边是连续升序）。

这一条，就是"改造版二分"的额外成本，而在普通有序数组里，这个判定永远是"左、右两边都升序"，于是是冗余信息。

用"有序的一半"排除另一半：不用管跳跃点

一旦知道哪一半是连续升序，就可以像普通二分一样，做区间判断：algo+1​

如果左半有序（nums[left] <= nums[mid]）：

• 如果nums[left] <= target < nums[mid]，说明 target 一定在左半 [left, mid-1]，于是收缩右端：right = mid - 1；
• 否则，target 不可能在这段升序区间里，只能在右半，收缩左端：left = mid + 1。

如果右半有序（nums[mid] <= nums[right]）：

• 如果nums[mid] < target <= nums[right]，说明 target 一定在右半 [mid+1, right]，于是left = mid + 1；
• 否则，target 只能在左半，right = mid - 1。

整个过程中，完全不需要显式"找跳跃点"：designgurus+1​

• 若跳跃点在被丢掉的那一半里，直接连同那一半一起被扔掉；
• 若跳跃点在保留下来的这一半里，下一轮再继续"哪边有序 + 用有序边排除另一边"，区间会越来越小，直到跳跃点的存在不再影响"哪边有序"的判断。

可以把"跳跃点"当成一个被动角色：它只是跟着被划分的区间一起被缩小或丢弃，从头到尾都不需要专门处理。

和普通二分有什么本质区别？

从"决策依据"的角度看，两者的核心差异是：geeksforgeeks+2​

普通二分（整体升序）：

• 强前提：对任意 mid，左侧所有元素 < nums[mid]，右侧所有元素 > nums[mid]。
• 决策只要看：
  • target < nums[mid]⇒ 去左边；
  • target > nums[mid]⇒ 去右边。
• 不需要看 nums[left] / nums[right]，因为"整体单调"已经隐含"左边都小，右边都大"。

旋转数组上的二分：

• 整体不单调，左半和右半都可能混有大值和小值。
• 若只看 target vs nums[mid]，会有很多例子把真正答案那半边排除掉。
• 因此必须先做一步：
  • 用 nums[left] / nums[mid] / nums[right] 判断哪一半是**"当前这一步中，仍然是连续升序"的那一边**；
  • 然后只在这半边里，用普通二分的区间逻辑判断 target 在不在这段，从而决定缩小到哪一边。airtribe+1​

于是，你可以把本题常用写法视为一个更通用的二分模板：

1. “先定位有序半边”——保证要用它做判断的一整段是单调升序的。
2. “再在这段里用普通二分逻辑排除另一半”。

在普通升序数组上，这套模板也成立，只是"哪边有序"的判断永远得出"两边都有序"，于是那部分变成冗余；在旋转数组上，则是必需的。notes.suhaib+1​

官方推荐方案与替代方案

LeetCode 官方题解以及主流教程，推荐的就是上面这套"一次改造版二分"：在一个 while 循环里完成"判断哪边有序 + 区间排除"，时间复杂度 O(log⁡n)，空间 O(1)。leetcode+2​

另一个等价的经典方案是"先找旋转点，再做普通二分"：geeksforgeeks+1​

1. 先用二分找到最小值下标（旋转点），把数组逻辑上分成两段升序。
2. 再根据 target 与 nums[0] 的大小，决定在前段还是后段上做普通二分。

这两种方法复杂度一样，本质上利用的是同一个性质：

"升序数组经过一次整体旋转后，依然有一半是连续升序，可以当作普通有序区间来二分。"algo+1​

如果你想写一篇自己的博客，可以直接用这四个板块组织结构：

1. 旋转数组的形状与"唯一一次掉下去"的性质；
2. 为何 nums[left] <= nums[mid] ⇒ 左半有序；
3. 在有序半边上如何像普通二分一样排除另一半；
4. 这套逻辑如何同时覆盖"普通二分"和"旋转二分"，成为一个通用模板。