LeetCode 33. 搜索旋转排序数组：在「局部有序」中二分

题目：整体无序的数组怎么二分

LeetCode 33：升序数组在某个点旋转（[0,1,2,4,5,6,7] → [4,5,6,7,0,1,2]），在 O(log n) 内找 target 的下标，找不到返回 -1。

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

「二分的前提」被打破：二分需要「单调性」——旋转数组整体不单调——「标准的二分模板」直接失效（mid 与 target 比较无法决定方向——「困境」：要求 O(log n)，但「无序」让二分失效——「出路：找到新的不变量」——「旋转数组的关键性质」：「从中点切开，必有一半是有序的」——「旋转点只有一个」——切开后至少一半不含旋转点——「有序的那一半」可以正常二分判断。

判断「哪一半有序」与 target 的归属

「哪半有序」的判断：nums[left] 与 nums[mid] 比较——「nums[left] <= nums[mid]」→ 左半有序（左半是单调递增段——「等号」的细节（left == mid（两元素区间——「等号」的处理（相等时左半视为有序（单元素必有序——「=」不能省——省掉等号在两元素时误判。「target 在不在有序半」的判断：「nums[left] <= target < nums[mid]」→ target 在左半——「区间判断」——在 → 右边界收缩到 mid-1（去有序半找）；不在 → left = mid+1（去另一半找）——「另一半」虽然无序，但它也「必有一半有序」——递归地成立——「有序半收缩」的每一步**——总有一次砍到 target。

def search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        if nums[left] <= nums[mid]:              # 左半有序
            if nums[left] <= target < nums[mid]:
                right = mid - 1                  # 在有序左半
            else:
                left = mid + 1                   # 去另一半
        else:                                     # 右半有序
            if nums[mid] < target <= nums[right]:
                left = mid + 1                   # 在有序右半
            else:
                right = mid - 1
    return -1

「旋转点」的另一个思路：「先找旋转点，再两段二分」——旋转点 = 全局最小值的位置（「找最小值」的 LeetCode 153——nums[mid] > nums[right] → 最小在右半——「与 right 比」的技巧（与 left 比在旋转数组有歧义——「与 right 比」是找最小值的正确姿势——「旋转点」的两段二分——「两种解法的对比」：一次二分（判断复杂）vs 两次二分（先找断点再分段——「两次二分」更简单、「一次二分」更快——「面试的双解展示」。

graph TD
    A[mid 切两半] --> B{左半有序?<br/>nums[left] <= nums[mid]}
    B -->|是| C{target 在有序左半?}
    B -->|否| D{target 在有序右半?}
    C -->|是| E[收缩到左半]
    C -->|否| F[去右半]
    D -->|是| G[收缩到右半]
    D -->|否| H[去左半]
    E & F & G & H --> I[每步砍一半 O(log n)]

「二分的本质条件」的再认识

「单调性」的重新定义：二分的本质不是「数组有序」——「判定条件的单调性」——「存在一个分界点：左边全假、右边全真（或反之）」——「二分找的是分界点」——旋转数组里「target 在不在 [left..mid]」的判断虽然复杂，但「每个决策都在收缩范围」——「决策的收敛性」是二分的本质——「单调性」的广义化：「数值单调」只是最常见的形式——「判定函数的单调」才是本质——「答案二分」篇（爬楼梯篇的延伸——「验证函数」的单调判定——「旋转数组的练习」是为了建立「广义二分」的直觉。

「有重复值」的坑（LeetCode 81）：「旋转数组含重复」：[1,0,1,1,1]——「nums[left] == nums[mid]」无法判断哪半有序——「解法：left += 1 缩边界」（无法判断就缩小——「最坏 O(n)」（重复值多时退化——「从 O(log n) 到 O(n)」的退化——「重复值」破坏了「判断的单调性」——「81 是 33 的进阶陷阱——「没有重复」的假设是 33 的前提——「前提的破坏」导致复杂度退化——「前提意识」：每个算法的复杂度都有前提——「前提被破坏时」的应对——**「缩小边界」是最诚实的应对。

超时体系高频问答

收尾前回答两个高频问题。「超时设多长合适？」——方法论的答案：「超时的设定方法」：P99 基线法（「P99 × 系数」的设定（P99 的 1.5-2 倍——「SLA 反推」（上游的 SLA 决定下游的超时——「SLA 链」的分解——「超时的迭代」（压测校准。「超时与重试怎么配合？」——预算制：「总预算 = 超时 × 重试 + 退避」——「上层超时 ≥ 预算」——「重试的幂等」前提（非幂等不重试——「预算链」逐层分解。超时体系的问答收束：超时体系的三个心智模型——「金字塔是权力结构（下层超时短、权力小）、预算是发薪日（下层花完了上层才补）、铁三角是互锁（超时-重试-熔断一起调）」——「超时的倒挂」是最常见的配错——**「从底层往上推算」的配置顺序——最便宜的稳定性，从一行配置开始。

旋转数组二分的进阶：LeetCode 81 的重复值陷阱与「二分前提的崩塌」

旋转数组二分的进阶：LeetCode 81 的重复值陷阱与二分前提的崩塌分析。「LeetCode 81 的重复值陷阱」：「重复值导致的判断失效」：[1,0,1,1,1]——「nums[left] == nums[mid]」（1 == 1——「无法判断哪半有序」——「左半有序」的前提被破坏——「判断的失效」——「失效的原因」（重复值让「left <= mid」不再保证「左半单调」——「[1,0,1] 的左半」（1,0 不单调——「前提崩塌」。「81 的应对」：「left += 1 的缩小边界」——无法判断时缩小左边界——「缩小的安全性」（nums[left] == nums[mid]——left 不是 target（mid 不是 target 已确认——「left 可以安全丢弃」——「丢弃的正确性」——「缩小的代价」（最坏 O(n)——「从 O(log n) 退化到 O(n)」——「退化的条件」（大量重复值——「[1,1,1,1,1] 的最坏」——全部相等——「每次都缩 1」——O(n)——「退化」的不可避免——「重复值与二分」的根本矛盾——「二分的对数效率」依赖「每次砍一半」——重复值破坏「砍一半的判断」——「矛盾的根源」。「LeetCode 153 的旋转最小值」：「找旋转点」的独立问题——「与 right 比较的技巧」——「nums[mid] > nums[right]」→ 最小在右半——「与 right 比」的原因（「left 侧在旋转数组可能无序」——「right 侧的判断」——「nums[mid] < nums[right]」→ 最小在左半或就是 mid——「最小值的定位」——「153 的无重复」与「154 的有重复」——「154 的重复处理」——同样 left += 1。「二分前提的崩塌」的深层教训：「每个算法的复杂度都有前提」——「前提的清单」：二分（有序或可判定）、快排（无重复或三路）、「哈希 O(1)」（无碰撞攻击、「递归 O(log n) 栈」（树平衡——「前提意识」的养成——「前提被破坏时」的三种应对：降级（接受 O(n)）、切换（换算法）、预处理（消除重复——「三种应对」的选择——「成本与收益」的权衡——「预处理消除重复」的成本（去重的开销——「去重」的 O(n)——「总成本」（去重 O(n) + 二分 O(log n) = O(n)——「直接线性搜索」也是 O(n)——「预处理+二分」不优于直接搜索——「结论」：重复值场景直接用线性搜索——「前提破坏时的最简应对」——「不要为了用高级算法而绕路」——「简单直接」的智慧。旋转数组二分的进阶总结：81 的重复值陷阱（判断失效+left += 1 的应对+O(n) 退化）+153 的最小值定位（与 right 比较的技巧）+二分前提的深层教训（前提清单+崩塌应对+简单直接）——「旋转数组二分」的教学价值：它暴露了「二分的前提条件」——不是所有「看似有序」的数组都能二分——「前提的检查」是使用任何算法前的必要步骤——「算法的前提意识」是高级工程师的标志——「知其然、知其所以然、知其所以然的前提」——三层认知——「第三层」：知道前提被破坏时怎么办——「三层」：会用→懂原理→懂边界——「懂边界」的工程师能判断「什么时候不该用这个算法」——「不该用」的判断力与「该用」同样重要——「这就是为什么 81 和 153 是二分学习的必经之路**。

一次二分与两次二分的取舍：可读性、可测性与族谱

正文给出了「一次二分」的完整判断链，这里把工程上同样常用的「两次二分」摊开对比。「两次二分的实现」：先跑一遍 153 题（找旋转点 = 全局最小下标），把数组切成两个升序段，再判断 target 落在哪一段、对那段跑一个最普通的二分——三段代码各自只有十来行，每段都能单独写单测：153 的测试集（未旋转、旋转点在头尾、两元素）与普通二分的测试集互相独立，出问题时能立刻定位是「找点错了」还是「找值错了」。一次二分恰恰相反：四类判断分支（左半有序/右半有序 × target 在/不在）纠缠在同一个循环里，等号出现在三个位置（left <= mid、target 的上下界各一处），任何一处写错都表现为「某些用例过、某些不过」——分支纠缠的代码，调试成本远高于代码行数。「取舍的结论」：线上代码与追求可维护的实现选两次二分（多一次对数级的常数开销，换来模块化与可测性）；追求单次循环的极致、或面试官明确要求「一次二分」时，才上判断链——而且面试里先写完两次二分、再口述「我知道一次二分的思路与等号陷阱」，通常比磕磕绊绊写对一次二分得分更高。「等号的记忆法」：与其背三个等号，不如记一条规则——「等号跟『相等时该往哪边走』走」：nums[left] <= nums[mid] 的等号，在 left == mid（两元素区间）时保证左半被判定为有序；target 上下界的等号，决定「端点命中归哪半」——用「相等时哪个分支是安全的」倒推等号位置，比背模板抗变体。「族谱收束」：33（无重复找值）、81（有重复找值，left += 1 保平安）、153（无重复找最小，与 right 比）、154（有重复找最小）——四题共享同一个不变量「切开后必有一半有序」，差异只在「找什么」与「有没有重复」：找值加归属判断、找最小比 right、有重复一律退化为缩边界。把四题画成一棵树（根是「一半有序」不变量，第一层分叉是找值/找最小，第二层是无重复/有重复），比分别背四份代码牢固得多——族谱式复习，是题目越刷越少的唯一办法。

小结

旋转排序数组二分的完整解析：关键性质（旋转点只有一个——「切开后必有一半有序」——有序半可正常判断）；解法（判断哪半有序 → 判断 target 是否在有序半 → 收缩或去另一半——「每步砍一半」保住 O(log n)——「等号」不能省）；双解法（一次二分的复杂判断 vs 两次二分（先找旋转点）——「简单与效率」的权衡）；本质的升华（「二分的本质是判定条件的单调性」——数值有序只是特例——答案二分、旋转数组、抽象的单调判定——「广义二分」的直觉）；81 的陷阱（重复值破坏判断——「退化到 O(n)」——前提意识）。给学习者的核心训练：「局部有序的识别」——拿到一个「看似无法二分」的问题，问：「切开后有没有一半满足某种单调性质？」——有的话，二分就还活着——「这个练习」训练的是「在看似无序中找到可利用的结构」**——这是二分查找从「套路」升华为「思维工具」的关键一步。

旋转数组的二分教会我们：二分的前提不是「有序」，是「存在可判定的收缩方向」——找到那个不变量，无序之中也能对半分。