断裂轨道上的目标搜索

旋转数组不是乱序，只是有序轨道被切开重接

给一个原本升序的数组，在某个未知位置被切一刀、整段平移拼接，比如 [0,1,2,4,5,6,7] → [4,5,6,7,0,1,2]。要求在 O(log n) 时间内找 target 的下标。本页用轨道 + 裂缝 + 雷达三件道具，把『为什么 mid 之后总有一半是有序的』画成你能跟着复述的动画。

旋转数组 · 单断点变形二分 · 哪半有序时间 O(log n)空间 O(1)

第一屏 · 什么是『旋转数组』

Stage 0 · 原始升序轨道

整条 [0,1,2,4,5,6,7] 没有任何裂缝，是普通的有序数组。

『旋转』在这道题里 ≠ 打乱顺序，而是『切一刀 + 平移拼接』。
因此最终数组里只产生一个断点（红色裂缝）。
裂缝两侧仍然是升序的——这就是后面二分还能用的根本原因。

第二屏 · 当前搜索用例

nums = [4, 5, 6, 7, 0, 1, 2]target = 0期望 → idx=4

帧 1/12第 0 轮

第三屏 · 主动画舞台

青=l · 琥珀=mid · 紫=r · 翠绿=有序半 · 红=裂缝

普通方块有序半 · 可二分命中被丢弃 · 坍缩裂缝 · 唯一断点l 探针r 探针

当前步骤旁白

舞台启动 · 区间 [0, n−1]

把候选区间 [l=0, r=6] 罩在整条轨道上。注意红色裂缝在下标 3|4 之间——那是当年那一刀的痕迹。整个搜索过程里裂缝只此一处，因此每次 mid 把区间切两半后，裂缝最多只能落入其中一半，另一半必然完全升序。

l=0 · r=6 · 区间长度 7 · target=0输入：[4,5,6,7,0,1,2], target=0

第四屏 · 当前决策卡

第 0 轮

while (l <= r) 即将开始第一轮迭代。

决策树 · 永远先问哪半有序

① nums[mid] === target ?
   ├─ yes → return mid
   └─ no  ↓
② nums[l] <= nums[mid] ?  ← 哪半有序
   ├─ yes（左半有序）
   │   └─ ③L  nums[l] <= target < nums[mid] ?
   │       ├─ yes → r = mid-1
   │       └─ no  → l = mid+1
   └─ no （右半有序）
       └─ ③R  nums[mid] < target <= nums[r] ?
           ├─ yes → l = mid+1
           └─ no  → r = mid-1

第五屏 · TypeScript · 同步高亮

while (l <= r)

1function search(nums: number[], target: number): number {
2  let l = 0;
3  let r = nums.length - 1;
4 
5  while (l <= r) {
6    const mid = Math.floor((l + r) / 2);
7 
8    if (nums[mid] === target) return mid;
9 
10    if (nums[l] <= nums[mid]) {
11      if (nums[l] <= target && target < nums[mid]) {
12        r = mid - 1;
13      } else {
14        l = mid + 1;
15      }
16    } else {
17      if (nums[mid] < target && target <= nums[r]) {
18        l = mid + 1;
19      } else {
20        r = mid - 1;
21      }
22    }
23  }
24 
25  return -1;
26}

循环条件用的是 l <= r（而不是 l < r），所以最后一帧 l == mid == r 仍然能比较一次—— 如果命中就在这一帧 return，否则才退出循环 return −1。

为什么这样写一定正确

核心证明

旋转数组只有一个断点。mid 把当前区间切成左右两段后，断点最多只能落在其中一段里，因此另一段一定保持升序。只要找到这段有序区间，就能像普通二分一样判断 target 是否在里面；如果不在，就可以安全丢掉这半边。

断点唯一C1

rotate 是一次平移，整条数组里只产生一个『大→小』的下降点。

至少一半有序C2

mid 切一刀后，两段加起来至多包含 1 个断点 → 必有一段无断点 → 必然升序。

在有序半做范围判断C3

只有完全升序的那段才能用 a ≤ target < b 这种普通比较，结论才可靠。

常见误区

误以为整个数组都无序P1
旋转数组仍然有强『局部有序性』——两段都升序。普通二分的范围比较，只是要先选对那一段。
盲目比较 nums[mid] 与 targetP2
在跨断点的那半，nums[mid] < target 并不能说明 target 在右边。必须先判断哪半有序，再用那半做范围判断。
范围判断写错边界P3
左半有序时：nums[l] ≤ target < nums[mid]（左闭右开，因为 nums[mid] 已先比过一次）。右半有序时：nums[mid] < target ≤ nums[r]。
误用到带重复元素的版本P4
本题元素唯一；如果有重复元素，会变成 LC81 Search in Rotated Sorted Array II，nums[l]==nums[mid]==nums[r] 时无法判断哪半有序，要左右各退一格。

第六屏 · 面试 30 秒回答

模板

『旋转数组本质是『升序数组被切一刀后整段平移再拼接』，所以只有一个断点。我每次取 mid 后断点最多落在一段里，另一段必然完全升序。算法就是：先比较 nums[l] 与 nums[mid] 判断左半是否有序；如果左半有序，看 target 是不是落在 [nums[l], nums[mid]) 里——落入就把 r 收到 mid-1，否则把 l 推到 mid+1；如果左半不有序，对称地用右半 (nums[mid], nums[r]] 做判断。每轮区间砍半，复杂度 O(log n)，空间 O(1)。』

当前用例

nums[4,5,6,7,0,1,2]

target0

期望idx=4

时间O(log n)

空间O(1)

背诵口令：『先判哪半有序 → 再看 target 在不在那半 → 决定丢哪半』。