Search in Rotated Sorted Array II

LeeCode #81

Description:

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.

Example:

Note

Idea:

分析 允许重复元素，则上一题中如果 A[m]>=A[l], 那么 [l,m] 为递增序列的假设就不能成立了，比 如 [1,3,1,1,1]。 如果 A[m]>=A[l] 不能确定递增，那就把它拆分成两个条件： • 若 A[m]>A[l]，则区间 [l,m] 一定递增 • 若 A[m]==A[l] 确定不了，那就 l++，往下看一步即可。

这里用的search方式是[left, right).

Time: O(n).

Code:

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int begin=0;
        int end=nums.size();

        while(begin < end){
            int mid = begin + (end-begin)/2;
            if(nums[mid] == target) return true;

            if(nums[begin]<nums[mid]){
                if(nums[begin]<=target && target<nums[mid]) end=mid;
                else begin=mid+1;
            }
            else if(nums[begin]>nums[mid]){
                if(nums[mid]<target && target<=nums[end-1]) begin = mid+1;
                else end=mid;
            }
            else{ // 有可能是begin==mid，也有可能是遇到duplicates了
                begin++;
            }
        }
        return false;
    }
};