LeetCode 81. 搜索旋转排序数组 II

2026-04-16 HGNULB 约 9 分钟

文章信息 9 个分类 3 个标签

分类

LeetCode CodeTop 中等未解决需加强历史考题 2-5 字节跳动百度

题目描述

✅ 81. 搜索旋转排序数组 II

题意分析

给定一个原本非降序、之后在某个下标处整体旋转过一次的数组 nums，判断 target 是否存在，只要返回 true / false，不需要给出下标。与 33 题唯一的差别是：本题允许元素重复。

输入不是有序的，却仍然保留着「两段各自有序」的结构：旋转点把数组切成前后两段，每段内部非降，且前段的所有值都不小于后段的所有值。题目给出的这种结构性信息，配合「只问存在性」的要求，指向的是每轮丢掉一半候选区间的做法，而不是从头扫到尾。

但重复元素会破坏「靠端点值判断哪一段有序」的前提。像 [1,0,1,1,1] 这样，中点值和右端点值相等时，目标既可能藏在左边也可能藏在右边，端点提供的信息量为零。这正是本题相对 33 题多出来的全部难度，也决定了最坏情况下无法保证对数级的效率——全数组同值时（如 [1,1,1,1,1] 找 0），任何比较都区分不出两侧，只能退化成逐个排除。

边界上要注意：数组长度可能为 1；旋转量可能为 0（即数组根本没被旋转，仍然完全有序）；target 可能不存在。这三种情况都应该被主逻辑自然覆盖。

解法：二分查找 + 去重

核心思路

暴力做法是线性扫描，$O(n)$ 且完全没用上「分段有序」这个条件，面试里给不了分。要提速就必须做到每轮排除一半，那就得回答一个问题：站在 mid 上，怎么知道 target 在哪半边？

观察点是：mid 把区间切成 [left, mid-1] 和 [mid+1, right] 两半，由于整个区间最多只有一个旋转点，这两半里至少有一半是完全有序的。有序的那一半可以用端点值做区间判定，直接确定 target 在不在里面；不在里面就整段丢掉，转到另一半。这就是本解法的核心机制——不是直接判断 target 在哪边，而是先找出「可判定」的那一边。

用 nums[mid] 与右端点 nums[right] 比较来识别有序段：nums[mid] < nums[right] 说明 [mid, right] 中间没有跨过旋转点，右半有序；nums[mid] > nums[right] 说明旋转点落在 (mid, right] 内，于是 [left, mid] 有序。两者相等则信息缺失。

这里的循环不变量是：若 target 存在于原数组，它一定存在于当前闭区间 [left, right] 内。三条分支都必须保持这个不变量。前两条分支靠有序段的区间判定保持；第三条分支 nums[mid] == nums[right] 时执行 right--，其正确性来自一个单独的论证：此时 nums[right] 的值与 nums[mid] 相同，而 mid 仍在区间内，所以丢掉 right 这一个位置不会丢掉「值为该数」的最后一份证据，答案不受影响。注意这是只丢一个位置，不是丢一半，不变量保住了但效率保不住。

区间用闭区间 [left, right]，循环条件 left <= right，退出时区间为空即判定不存在。

解题步骤

初始化 left = 0、right = n - 1：闭区间要覆盖全部下标，所以 right 取 n - 1 而不是 n。区间语义一旦定下来，后面每一处边界更新都必须与之配套。

循环条件写 left <= right：闭区间下 left == right 仍然是一个合法的、含一个元素的待查区间，写成 < 会漏掉最后一个元素。

mid = left + (right - left) / 2：这样写而不是 (left + right) / 2，是为了避免两个大下标相加溢出 int。

先判 nums[mid] == target 就返回：本题只要存在性，命中即可结束，不需要继续收敛到边界。这一步放在最前面还有个好处——后面三条分支都可以默认 nums[mid] != target，判定条件里的等号边界更容易想清楚。

nums[mid] < nums[right]：右半有序。此时用 nums[mid] < target && target <= nums[right] 判定 target 是否落在 (mid, right]。左边界不取等是因为 nums[mid] 已被排除，右边界取等是因为 nums[right] 还没被检查过。落在里面就 left = mid + 1，否则 right = mid - 1。

nums[mid] > nums[right]：左半有序。改用左端点判定 nums[left] <= target && target < nums[mid]，落在 [left, mid) 就 right = mid - 1，否则 left = mid + 1。注意这里两个等号的位置与上一条恰好相反，因为被排除的端点换了一侧。

nums[mid] == nums[right]：无法判定，执行 right--。这是唯一一条不折半的分支。不能写成 left++，因为判定用的参照点是右端点，收缩右端才与判定逻辑自洽；也不能同时收两端，那会丢掉尚未检查的位置。

循环正常退出返回 false：区间空了说明 target 不在数组里。

以 nums = [1,0,1,1,1]、target = 0 走一遍（这是本题最典型的用例，普通二分会在这里出错）。

初始 left = 0、right = 4。第一轮：mid = 2，nums[2] = 1 != 0；比较 nums[2] = 1 与 nums[4] = 1，相等，落入去重分支，right-- 变成 3。此刻若换成 33 题的写法，会误判右半有序并把整个左半（含答案 0）丢掉，直接返回 false。

第二轮：区间 [0, 3]，mid = 1，nums[1] = 0 == target，返回 true。

再看一个不存在的用例 nums = [1,1,1,1]、target = 2：四轮里 nums[mid] 与 nums[right] 始终相等，right 依次从 3 缩到 -1，left > right 退出，返回 false。这一遍走查同时说明了最坏情况下为什么是 $O(n)$。

代码实现

class Solution {
    // 重复元素会让 nums[mid] == nums[right] 时无法判断哪边有序，此时只能收缩 right 去掉一。
    public boolean search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return true;
            }

            if (nums[mid] < nums[right]) {
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            } else if (nums[mid] > nums[right]) {
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                right--;
            }
        }

        return false;
    }
}

func search(nums []int, target int) bool {
    // 重复元素会让 nums[mid] == nums[right] 时无法判断哪边有序，此时只能收缩 right 去掉一。
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] == target {
            return true
        }

        if nums[mid] < nums[right] {
            if nums[mid] < target && target <= nums[right] {
                left = mid + 1
            } else {
                right = mid - 1
            }
        } else if nums[mid] > nums[right] {
            if nums[left] <= target && target < nums[mid] {
                right = mid - 1
            } else {
                left = mid + 1
            }
        } else {
            right--
        }
    }

    return false
}

复杂度分析

时间复杂度：平均 $O(\log n)$，最坏 $O(n)$。凭什么：前两条分支每轮把区间折半，共 $O(\log n)$ 轮；但去重分支每轮只缩掉一个位置，当数组元素几乎全相同时（如 [1,1,...,1] 找一个不存在的值），整个过程退化为逐位收缩的线性扫描，这是重复元素带来的固有代价，无法通过改写规避。

空间复杂度：$O(1)$。凭什么：全程只维护 left、right、mid 三个下标变量，没有递归栈也没有额外数组。

关键点总结

旋转有序数组二分的通用套路是「先找出必然有序的那一半，再用端点值做区间判定」，而不是直接猜 target 在哪一侧——这个思路顺序讲清楚了，33、81、153、154 就是同一道题的四个变体。

判定条件里的等号位置由「哪个端点已被排除」决定：以 nums[mid] 为界的一侧不取等，未检查过的端点一侧取等。面试时能主动解释这两处不对称，比背下代码更有说服力。

遇到无法判定的情形，退一步只收缩一个位置、保住不变量，是二分类问题的通用兜底手法：宁可牺牲复杂度，也不能牺牲正确性。

复杂度退化到 $O(n)$ 不是实现缺陷而是问题本身的下界，面试官问「能不能做到严格 $O(\log n)$」时，正确回答是不能，并用全同数组举反例说明任何比较都无法区分两侧。

闭区间 [left, right] + left <= right + mid ± 1 是一套必须整体配套的模板，任何一处改了另外两处也要跟着改。

易错点总结

直接套用 33 题代码不加去重分支：nums = [1,0,1,1,1]、target = 0 时 nums[mid] = nums[right] = 1，会被误判成「右半有序」，从而把含答案的左半整段丢弃，返回 false。

去重分支写成 left++：nums = [1,1,1,0,1]、target = 0 时判定参照的是右端点，收左端会与判定逻辑脱节，可能在收到 left > mid 后落入错误分支而漏判。

去重分支写成 left++; right-- 同时收：nums = [1,0,1]、target = 0 时首轮 mid = 1 命中前若先双向收缩，会把尚未检查的下标一次丢两个，可能直接跳过答案。

有序判定用 nums[mid] >= nums[left] 代替与右端比较，却不处理相等：nums = [1,1,1,0,1] 这类左端与中点相等的用例会被误判成左半有序，target = 0 时返回 false。

右半有序分支的区间判定写成 nums[mid] <= target：nums[mid] 已经确认不等于 target，写成小于等于虽不致错但会让人误以为 mid 仍是候选，紧接着若把 left 更新为 mid 就会死循环。

左半有序分支忘记用 nums[left] 而复用 nums[right]：nums = [4,5,6,7,0,1,2]、target = 5 时判定条件恒假，会一路把 left 推到右侧，返回 false。

循环条件写成 left < right：nums = [1]、target = 1 时区间 [0,0] 一轮都不进，直接返回 false。

mid 写成 (left + right) / 2：下标接近 Integer.MAX_VALUE 的极端场景下会溢出成负数，触发数组越界异常。

边界更新写成 right = mid 或 left = mid：nums = [3,1]、target = 1 时 mid 停在 0 不动，区间不再收缩，程序死循环超时。

相似题目

题目	难度	考察点
33. 搜索旋转排序数组	中等	无重复元素，端点比较永不相等，可去掉去重分支并严格保证 $O(\log n)$
153. 寻找旋转排序数组中的最小值	中等	不给 target，改为收敛到旋转点本身，用开区间与 `left < right` 模板更顺手
154. 寻找旋转排序数组中的最小值 II	困难	本题的求最小值版本，同样在端点相等时退化，去重分支的正确性论证与本题完全同源
剑指 Offer 11. 旋转数组的最小数字	简单	与 154 同题，只是数据规模更小，常被用作去重分支的入门练习
面试题 10.03. 搜索旋转数组	中等	有重复且要求返回最小下标，命中后不能立刻返回，还要继续向左收敛
162. 寻找峰值	中等	数组无序，靠相邻元素的升降趋势而非端点值来决定丢弃哪一半
704. 二分查找	简单	无旋转的裸模板，用来对照闭区间三件套（循环条件、`mid ± 1`、返回值）的配套关系