题目描述

Follow up for "Search in Rotated Sorted Array":What if duplicates are allowed?
Would this affect the run-time complexity? How and why?

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7
might become 4 5 6 7 0 1 2
).
Write a function to determine if a given target is in the array.
The array may contain duplicates.

和之前的旋转数组相比，如果增加重复元素这一限制，最终算法会有什么影响？如果旋转数组里有指定的元素，则返回true，否则返回false

代码及注释

class Solution {
public:
    int search(vector<int>& nums, int target) {
        // 线性表搜索问题一般都会用到二分法
        // 二分法涉及三个指针min max mid
        int min = 0, max = nums.size()-1;
        // 二分法最终的停止条件
        while(min <= max){
            // 初始第一次二分的mid
             int mid = (min+max)/2;
             // 如果mid恰好是target(最终target都会到mid这里)
             if(nums[mid] == target)    return true;
             // 如果左半部分有序,则在此半部分（有序字符串）进行二分查找
             if(nums[min] < nums[mid]){
                 if(nums[min]<=target && target<nums[mid])
                    max = mid - 1;
                else
                    min = mid + 1;
             }else if(nums[min] > nums[mid]){
                 if(nums[mid]< target && target<=nums[max])
                    min = mid + 1;
                else
                    max = mid - 1;
             }else{
                 min++;
             }
        }
        // 不满足最高二分条件min<max时
        return false;
    }
};

分析

由于重复元素的存在，上一题判断是否有序（递增）的方式：nums[min] <= nums[mid] 不再成立。那么可以把之前的两部分判断分成三部分：

• nums[min]<nums[mid]：则[min,mid]递增；
• nums[min]=nums[mid]：跳过，min++