Leetcode 81: search in rotated sorted arrayII

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.

 存在duplicates的时候，可能只判断mid , left 和 right的值是不能正确表示元素顺序走向的， 当存在mid == left的时候，需要将left 向mid移动一步，看是不是能走出重复的区域， 所以在判断的时候， 可以以left为基地， mid < left, mid > left, mid == left， 或者以right为基点，那样的话如果mid == right,将right向mid移动一步。 

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        //sanity check
        if (nums.size() == 0) return false;
        int left = 0;
        int right  = nums.size()-1;
        while (left <= right) {
            int mid = left + (right - left)/2;
            if (nums[mid] == target) return true;
            //case 1: left->mid ascending
            if (nums[left] < nums[mid]) {
                if (nums[mid] > target && target >= nums[left]) {
                    right = mid-1;
                } else {
                    left = mid + 1;
                }
            } else if (nums[mid] < nums[left]) {//case 2: mid-right ascending
//not nums[mid] < nums[right])
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid+1;
                } else {
                    right = mid -1;
                }
            } else {
               left++; // time complexity: O(n)
            }
        }
        return false;
    }
};