Search in Rotated Sorted Array 旋转数组查找

int search(vector<int>& nums, int target) {
    int start=0;
    int end=nums.size()-1;
    while(start<=end) {
        int mid=(start+end)>>1;
        if (nums[mid]==target) return mid;
        if (nums[mid]>=nums[start]) {
            if (target<nums[mid] && target>=nums[start]) {
                end=mid-1;
            } else {
                start=mid+1;
            }
        } else {
            if (target>nums[mid] && target<=nums[end]) {
                start=mid+1;
            } else {
                end=mid-1;
            }
        }
    }
    return -1;
}

bool search(vector<int>& nums, int target) {
    int start=0;
    int end=nums.size()-1;
    while(start<=end) {
		// 除去重复元素
        while(start<end && nums[start]==nums[start+1]) ++start;
        while(end>start && nums[end]==nums[end-1]) --end;

        int mid=(start+end)>>1;
        if (nums[mid]==target) return true;
        if (nums[mid]>=nums[start]) {
            if (target<nums[mid] && target>=nums[start])
                end=mid-1;
            else
                start=mid+1;
        } else {
            if (target>nums[mid] && target<=nums[end])
                start=mid+1;
            else
                end=mid-1;
        }
    }
    return false; 
}