题目来源

• leetcode：81. 搜索旋转排序数组 II

题目描述

class Solution {
    
public:
    bool search(vector<int>& nums, int target) {
    

    }
};

题目解析

本题是leetcode：33. 搜索旋转排序数组的扩展，区别在于本题有重复元素。

我们知道，所谓的旋转其实就是「将某个下标前面的所有数整体移到后面，使得数组从整体有序变为分段有序」。

本题元素不唯一，这意味着我们无法直接根据nums[0]的大小关系，将数组分为为两段，即无法通过「二分」来找到旋转点。

因为「二分」的本质是二段性，并非单调性。只要一段满足某个性质，另外一段不满足某个性质，就可以用「二分」。

举个，我们使用数据 [0,1,2,2,2,3,4,5] 来理解为什么不同的旋转点会导致「二段性丢失」：

class Solution {
    

public:
    int search(vector<int>& nums, int target) {
    
        int left = 0;
        int right = nums.size() - 1;
        while (left <= right){
    
            int mid = left + (right - left) / 2;
            if(nums[mid] == target){
    
                return true;
            }
            
            if(nums[left] == nums[mid]){
    
                left++;
                continue; // 跳到下个left
            }

            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;
    }
};