搜索旋转排序数组

挨个找当然行，可那就白白浪费了「旋转前本来有序」这个条件。题目都把有序明牌摆你面前了，必须把二分用起来。

转折：旋转数组虽整体无序，但从 mid 切两半，总有一半是完整升序（端点一比就知道：nums[l] ≤ nums[mid] 则左半有序，否则就是右半有序）。认出有序半后，只要看 target 在不在那半的范围里就能决定丢哪边——照样每步砍一半。

准备 · 闭区间 [0,6]：搜索范围是整个数组，l=0、r=6。要找的 target = 0。

第 1 轮 · 取 mid：中点 mid=3 处是 7，不等于目标 0。先判断哪半有序。

第 1 轮 · 判有序半：比端点：nums[l]=4 小于等于 nums[mid]=7，说明左半 [4,5,6,7] 是有序的（高亮那段）。那就拿 target 和这个有序半的范围比。

第 1 轮 · target 不在有序半 → 去右半：0 不落在有序左半 [4,7)（含左端 4、不含已单独判过的 mid=7）里，所以它必在另一半。整个左半丢掉（灰），l 跳到 4。

第 2 轮 · 取 mid：只看右段 [0,1,2]。新中点 mid=5 处是 1，仍不等于 0。

第 2 轮 · 判有序半：同样先比端点：nums[4]=0 小于等于 nums[5]=1，左半 [0,1] 有序。拿 target 和它的范围比。

第 2 轮 · target 在有序半 → 收右：这次 0 正好落在有序左半 [0,1)（含左端 0、不含已单独判过的 mid=1）里，所以去这半找：丢掉 mid 右边，r 收到 4。

第 3 轮 · 命中！：区间只剩一个，mid=4 处正好是 0 = target。返回下标 4。每轮都砍掉一半，所以是 O(log n)。

注意：上面三轮 mid 都落在左半，比出来都是「左半有序」。可代码里还有个 else——当 nums[l] ＞ nums[mid] 时，是右半有序。换个例子把这条分支也跑一遍，套路才算闭环。

换例 · nums=[6,7,0,1,2,4,5]，找 5：换一个旋转得更狠的数组 [6,7,0,1,2,4,5]，要找的 5 在靠右那段。看 mid 落到小数那边会发生什么。

第 1 轮 · 取 mid：中点 mid=3 处是 1，不等于 5。照例先判哪半有序。

第 1 轮 · 判有序半 → 这次是右半！：关键差别来了：nums[l]=6 大于 nums[mid]=1，左半不再是升序——说明断点在左边，反而是右半 [1,2,4,5] 完整有序（高亮右段）。这就是代码里的 else 分支。

第 1 轮 · target 在右有序半 → 去右半：这回比的是右有序半的范围：5 落在 (1, 5] 里，所以去右半。丢掉 mid 左边（灰），l 跳到 4。注意这里收的是 l，正好和左半有序那支相反。

第 2 轮 · 取 mid：剩下 [2,4,5]。新中点 mid=5 处是 4，还不是 5。

第 2 轮 · 判有序半：这小段又恢复成左半有序：nums[4]=2 小于等于 nums[5]=4。5 不在 [2,4] 里，所以去另一半，l 跳到 6。

第 2 轮 · 命中！：区间只剩 mid=6，正好是 5 = target。返回下标 6。两条分支（左半有序 / 右半有序）现在都跑通了。

旋转数组的二分，核心就这一句：哪半有序看得出来（端点比一下），target 在不在那半也看得出来（范围比一下）。剩下交给二分。

迁移阶梯：把这题练到能复述后，再去同类题里迁移：先复用「定有序半」的状态判断，再调整边界条件。也可以直接问问右侧的小欧：「LC81 有重复元素时这套二分会怎么退化？」

边界三连：边界三连：极端输入先过一遍。

几个高频追问，记住答法。