LeetCode 81. 搜索旋转排序数组 II - C# 实现

思路

与 33 题类似，使用二分查找，但数组可能包含重复元素。

当 nums[left] == nums[mid] == nums[right] 时，无法判断哪一半是有序的，此时只能收缩边界（left++、right–）。其余情况与 33 题一致：判断 mid 落在左半有序区还是右半有序区，然后在有序区间内判断 target 是否在范围内。

C# 代码

public class Solution {
    public bool Search(int[] nums, int target) {
        if (nums == null || nums.Length == 0) return false;
        
        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[left] == nums[mid] && nums[mid] == nums[right]) {
                left++;
                right--;
                continue;
            }

            // 左半部分有序
            if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } 
            // 右半部分有序
            else {
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return false;
    }
}

复杂度分析

指标 复杂度
时间 平均 O(log n)，最坏 O(n)（所有元素相同）
空间 O(1)

关键点说明

1. 去重收缩：当 nums[left] == nums[mid] == nums[right] 时，无法二分，只能排除 left、right 两个位置，退化为线性扫描。例如 [1,1,1,1,1,2,1]。
2. 判断有序区间：nums[left] <= nums[mid] 表示 [left, mid] 单调递增；否则 [mid, right] 单调递增。
3. target 落点判断：在有序区间内用普通二分判断，否则去另一侧继续查找。

测试用例

var s = new Solution();
Console.WriteLine(s.Search(new int[] {2,5,6,0,0,1,2}, 0)); // true
Console.WriteLine(s.Search(new int[] {2,5,6,0,0,1,2}, 3)); // false
Console.WriteLine(s.Search(new int[] {1,1,1,1,1,2,1}, 2)); // true
Console.WriteLine(s.Search(new int[] {1,1,1,1,1,2,1}, 3)); // false
Console.WriteLine(s.Search(new int[] {1,3,1,1,1}, 3));     // true
Console.WriteLine(s.Search(new int[] {3,1}, 1));           // true

与 33 题对比

33 题 81 题
元素 无重复 可重复
时间 O(log n) 平均 O(log n)，最坏 O(n)
额外步骤 无 三端相等时收缩边界