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

2026-04-16 HGNULB 约 5 分钟

文章信息 9 个分类 · 2 个标签

分类

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

标签

数组 二分查找

题目描述

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

题意分析

原数组按非递减顺序排列，允许重复值，再围绕某个位置旋转，得到现在的数组。判断目标是否存在，返回布尔值，不要求找出旋转位置或目标的第一个下标。

旋转之后仍保留两段有序结构，但重复值可能掩盖分界位置。与没有重复值的版本相比，关键是知道何时能够排除一半，何时只能安全地缩小一个边界。

解法：二分查找 + 去重

核心思路

[!blue]

用闭区间 [left, right] 保留全部尚未排除的目标位置。每轮先检查中点是否等于目标，命中立即返回；后续判断都建立在中点不是答案的前提上。

若 nums[mid] < nums[right]，中点到右端处于同一非递减段，右半有序。目标满足 nums[mid] < target <= nums[right] 时，保留中点右边；否则这一半不可能含目标，可以连同已排除的中点一起舍弃。

若 nums[mid] > nums[right]，从中点到右端跨过旋转分界，左端到中点则处于有序的较大段。目标满足 nums[left] <= target < nums[mid] 时保留左半，否则转向中点右边。

若中点和右端相等，数值没有提供分界在哪一侧的信息，不能据此砍掉半个区间。不过中点已经确认不等于目标，右端与它同值，也一定不是目标，因此只令 right--。这个动作保证不丢答案，但可能只排除一个位置，这正是重复值使最坏时间退化的原因。

解题步骤

1. 令 left = 0、right = n - 1，在 left <= right 时计算中点。
2. 中点等于目标就返回 true。
3. 中点小于右端时，根据目标是否位于右侧有序值域，保留右半或左半。
4. 中点大于右端时，根据目标是否位于左侧有序值域，保留左半或右半。
5. 两值相等时仅移除右端一个已确认不是目标的位置。
6. 候选区间为空时返回 false。

代码实现

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(n)$。能持续识别有序半段时为 $O(\log n)$；大量相等值使每轮只能执行一次 right--，不能保证折半，因此最坏线性。
• 空间复杂度：$O(1)$，只保存边界和中点。

关键点总结

[!green]

• 先判断中点命中，才能证明同值右端也不是答案。
• 大小关系明确时利用有序半段的值域排除；相等时只做有依据的单点排除。
• 只需保证存在的目标始终留在候选区间，不必预先定位唯一旋转点。
• 重复值增加无信息比较，影响最坏效率，而不是改变正确性要求。

易错点总结

[!yellow]

• 中点等于右端时仍直接舍弃一半，目标可能正藏在被删区间的不同值位置。
• 因中点等于右端就删除左端，左端并没有被证明同值或非目标，可能删掉唯一答案。
• 还未检查中点是否命中就删去同值右端，不能建立安全排除的前提。
• 使用 left < right 却没有单独检查最后位置，会遗漏单元素候选区间。
• 目标范围比较遗漏有序段外端点的等号，可能错过恰好位于左端或右端的目标。
• 将时间复杂度仍一概写成对数级，忽略重复分支只能排除一个位置。

相似题目

题目	难度	关联与区别
33. 搜索旋转排序数组	中等	不含重复值时能直接判断有序半区，本题重复值可能遮蔽旋转边界，需要额外缩边。
154. 寻找旋转排序数组中的最小值 II	困难	同样处理重复旋转数组中的无信息比较，原题只找最小值，本题判断目标是否存在。
153. 寻找旋转排序数组中的最小值	中等	利用旋转数组中仍有序的一半排除搜索区间；本题含重复值时处理无法判定有序侧的边界，该题比较中点与右端定位最小值。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/05902279

许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！