LeetCode 33. 搜索旋转排序数组：一次二分讲透「分段有序」

题目与约束

LeetCode 33「搜索旋转排序数组」的题面很短：一个元素互不相同的升序数组，在某个未知下标处被「旋转」了——截成两段后交换前后位置，例如 [4,5,6,7,0,1,2] 就是 [0,1,2,4,5,6,7] 旋转后的结果。现在要在这个数组里找 target，找到返回下标，找不到返回 -1，并且要求时间复杂度必须是 O(log n)。

O(log n) 这个要求直接排除了两条捷径：线性扫描是 O(n)；先排序再二分会把旋转带来的结构信息全部抹掉，排序本身也不止 O(log n)。命题意图很明显：你必须直接在「半有序」的数组上做二分查找。二分查找指的是每次与中间元素比较、把搜索范围缩小一半的策略，它通常依赖全局有序，而这题偏偏只是「分段有序」。

关键观察：任意切开，必有一半有序

整个数组不是全局有序的，二分似乎无从下手。但换一个视角：从任意位置 mid 切开，左右两半中至少有一半是完全有序的。

这不是巧合。旋转点（最小值所在的位置）只可能落在 mid 的一侧：如果 nums[left] <= nums[mid]，说明 [left, mid] 这段没有跨过旋转点，左半完全升序；否则旋转点落在左半段内，右半 [mid, right] 必然完全升序。两种情况覆盖全部可能，无一遗漏。

有了这个观察，判别逻辑就顺了：先判断哪一半有序，再看目标值是否落在有序那一半的取值区间内。落在，就去那一半找；不落在，去另一半找。无论走哪个分支，每一步都安全地扔掉一半——这正是二分的本质。

拿 [4,5,6,7,0,1,2]、target = 0 走一遍：第一轮 left=0, right=6，mid=3，nums[3]=7，nums[0]=4 <= 7 说明左半有序，但 0 不在 [4, 7) 里，于是 left = 4；第二轮 mid=5，nums[5]=1，nums[4]=0 <= 1 说明左半 [4,5] 有序，0 恰好落在 [0, 1) 里，于是 right = 4；第三轮 left == right == 4，nums[4]=0，命中返回。三轮下来，每一轮扔掉的都是被证明不含答案的那一半。

循环不变量：为什么不会丢答案

理解所有二分变体的钥匙是循环不变量（invariant）：一个在每轮循环开始与结束时都保持成立的命题。本题的不变量是：如果 target 存在，它一定在闭区间 [left, right] 内。

初始时区间覆盖整个数组，命题成立。每一轮根据「哪半有序、target 在不在有序半的区间里」收缩边界，被扔掉的那一半已被证明不含 target，命题依然成立。当 left > right 时区间为空，说明 target 不存在，返回 -1。有了不变量，边界怎么移动不再是背模板：把 left 挪到 mid + 1 或把 right 挪到 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]:              # 左半 [left, mid] 有序
            if nums[left] <= target < nums[mid]:
                right = mid - 1                  # 目标在有序的左半
            else:
                left = mid + 1                   # 目标只能去右半
        else:                                    # 右半 [mid, right] 有序
            if nums[mid] < target <= nums[right]:
                left = mid + 1                   # 目标在有序的右半
            else:
                right = mid - 1                  # 目标只能去左半
    return -1

三个高频易错点

mid 的写法。习惯写 mid = left + (right - left) // 2 而不是 (left + right) // 2。Python 的整数不会溢出，但在 Java、C++ 等语言里两个大下标相加可能溢出，这个习惯值得刻进肌肉记忆。
边界符号要配套。本题用 while left <= right 配 mid ± 1 的闭区间收缩；若换成 while left < right，更新方式就得相应改成 right = mid。两种风格混用会导致死循环或漏解，判断标准始终是：收缩之后，不变量还成立吗？
「哪半有序」的比较条件写反。判左半有序用的是 nums[left] <= nums[mid]，注意是 <= 不是 <：当区间只剩一两个元素时 left == mid，写成 < 会把「左半有序」误判成无序。而 target 落点的判断里，靠 mid 的一端用开区间即可，因为 nums[mid] == target 已经提前返回。

复杂度与延伸

时间复杂度 O(log n)——每轮严格把区间缩小一半；空间复杂度 O(1)。

另一条经典路线是「两步法」：先用一次二分找到旋转点（最小值下标），再对所在的有序段做一次普通二分。它把问题拆成两个标准子问题，好写好测，但要额外处理「目标落在哪一段」的判断与下标换算。本题的一次法则在同一次循环里同时完成「定位有序半」与「决策」，代码更短。面试里先讲清一次法的「分段有序」观察，再以两步法佐证，通常比单一解法更能体现理解深度。

顺带一提：本题「元素互不相同」的约定是关键。若允许重复（LeetCode 81 的变体），出现 nums[left] == nums[mid] == nums[right] 时无法判断哪半有序，只能把两端各收缩一格再继续，最坏情况退化到 O(n)。「分段有序」每一次安全丢弃的前提，是端点比较足以给出确定结论。

要点小结

核心观察：分段有序数组上，任意 mid 切开至少一半完全有序，据此每步扔掉一半。
用不变量「target 若存在必在 [left, right] 内」推导边界移动，不靠背模板。
易错点集中在三处：mid 防溢出写法、边界符号与更新方式配套、判有序的比较条件。