Search in Rotated Sorted Array II

解析：这道题是Search in Rotated Sorted Array的改进版，出现重复元素，它们之间的区别是，重复元素的出现导致无法准确定位有序序列的范围。例如：1 1 3 4 3，根本就无法根据nums[mid]和边缘位置元素的关系判断哪一边是有序的序列。解决的方法是，将nums[mid] == 边缘位置元素这种情况单独进行判断，即出现这种关系时，只缩小边缘位置的一步距离，这样就不会忽略掉目标元素
在序列[1, 1, 3, 4, 3]中查找4
1： 1, 1, 3, 4, 3 left = 0 right = 4
2： 1, 1, 3, 4, 3 left = 0 right = 3
3： 1, 1, 3, 4, 3 left = 2 right = 3
4： 1, 1, 3, 4, 3 left = 3 right = 3
5. return true

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        if (nums.empty()) return false;
        int left = 0;
        int right = nums.size() - 1;
        while (left <= right){
            int mid = (left + right) / 2; //取中间元素
            if (nums[mid] == target) return true;
            if (nums[mid] < nums[right]){
                if (target > nums[mid] && target <= nums[right]){ //有序序列
                    left = mid + 1;
                }
                else{
                    right = mid - 1;
                }
            }
            else if (nums[mid] > nums[right]){
                if (target >= nums[left] && target < nums[mid]){ //有序序列
                    right = mid - 1;
                }
                else{
                    left = mid + 1;
                }
            }
            else{ //去除重复元素，缩小搜索范围
                right--;
            }
        }
        return false;
    }
};