0081. Search in Rotated Sorted Array II

题目信息

题号:
  1. 搜索旋转排序数组 II

难度:

Medium

主题:

数组、二分查找、旋转有序数组、重复值

原题:

LeetCode 0081

重点:

从线性扫描,推导到重复端点消歧,再恢复有序半区二分

题目重述

给定一个非递减数组。它在某个未知下标处旋转后形成数组 nums,其中允许出现重复值。 判断整数 target 是否存在于 nums 中。

旋转表示把原数组分成前后两段,再交换两段顺序。例如:

原数组:[0,1,2,4,4,5,6]
旋转后:[4,5,6,0,1,2,4]

约束如下:

  • 1 <= nums.length <= 5000

  • -10^4 <= nums[i], target <= 10^4

自建示例

输入:nums = [4,4,5,6,0,1,2,4], target = 1
输出:true

目标位于旋转点右侧的有序段中。

输入:nums = [1,1,1,0,1], target = 0
输出:true

初始左端、中点和右端都等于 1,必须先移除没有顺序信息的重复端点。

输入:nums = [2,2,2,2,2], target = 3
输出:false

所有元素相同且都不是目标,二分查找会逐步退化为线性消歧。

C++ 实现

#include <vector>

class Solution {
private:
    bool linearScan(const std::vector<int>& nums, int target) {
        for (int value : nums) {
            if (value == target) {
                return true;
            }
        }
        return false;
    }

    bool discardOneDuplicateEnd(const std::vector<int>& nums,
                                int target) {
        int left = 0;
        int right = static_cast<int>(nums.size()) - 1;

        while (left <= right) {
            int middle = left + (right - left) / 2;

            if (nums[middle] == target) {
                return true;
            }

            if (nums[left] == nums[middle]) {
                ++left;
                continue;
            }

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

        return false;
    }

    bool discardBothDuplicateEnds(const std::vector<int>& nums,
                                  int target) {
        int left = 0;
        int right = static_cast<int>(nums.size()) - 1;

        while (left <= right) {
            int middle = left + (right - left) / 2;

            if (nums[middle] == target) {
                return true;
            }

            if (nums[left] == nums[middle] &&
                nums[middle] == nums[right]) {
                ++left;
                --right;
                continue;
            }

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

        return false;
    }

public:
    bool search(std::vector<int>& nums, int target) {
        return discardBothDuplicateEnds(nums, target);
    }
};

题解

线性扫描起点

直接检查每个元素一定正确,时间为 O(n)。要继续优化,必须利用旋转数组仍由两个非递减段组成这一结构。

没有重复值时,中点至少有一侧可以根据端点关系确定为有序段。若目标落在该段的值域内,就保留该段; 否则删除它。这样每轮可以排除约一半候选。

重复值造成歧义

数组 [1,0,1,1,1] 的初始状态为:

left = 0, middle = 2, right = 4
nums[left] = nums[middle] = nums[right] = 1

仅凭三个值无法判断旋转点在中点左侧还是右侧,因此也无法证明哪一半有序。 这不是二分模板的边界错误,而是重复值确实抹去了顺序信息。

单侧消歧

中点已经确认不等于目标。若 nums[left] == nums[middle],左端点也不等于目标,删除左端点是安全的:

++left

持续删除后,要么找到目标,要么出现 nums[left] != nums[middle],此时可以重新识别有序半区。 这种写法只需要一个消歧分支,最坏仍可能逐个删除元素。

双侧消歧

当三端值全部相等时,中点不是目标意味着左右端点也都不是目标,因此可以同时执行:

++left
--right

这比只删除左端点对全相等区间更直接。若只有一侧与中点相等,则仍可能通过另一侧的大小关系识别有序半区, 不能无条件同时删除两端。

有序半区

完成必要的消歧后,分两种情况。

nums[left] <= nums[middle] 表示左半区非递减。目标满足下面的半开值域时,只可能位于左半区:

nums[left] <= target < nums[middle]

否则搜索右半区。

若 nums[left] > nums[middle],旋转点位于左半区,右半区必然非递减。目标满足下面的值域时保留右半区:

nums[middle] < target <= nums[right]

左右条件采用不同的开闭边界,是因为中点已经检查过,不能再次保留在新区间中。

循环不变量

每轮开始时,若目标存在,则它一定仍位于闭区间 [left, right] 中。

  • 命中中点时立即返回。

  • 消歧只删除已知不等于目标的端点。

  • 有序半区判断只删除值域不可能包含目标的一半。

因此算法不会遗漏目标。区间耗尽时,所有可能位置均已排除。

退化原因

在 [2,2,2,2,2] 中查找 3 时,每轮都只能删除重复端点,无法按比例缩小区间。 所以该算法在歧义很少时具有二分查找的 O(log n) 行为,最坏时间为 O(n)。

重复值造成的信息缺失决定了这种最坏退化;常量空间算法无法保证每轮都排除一半元素。

复杂度

线性扫描时间为 O(n)。两种消歧二分在无大量歧义时为 O(log n),最坏为 O(n); 它们都只维护几个下标,额外空间为 O(1)。