bool search(vector<int>& nums, int target) {
        if(nums.empty())return false;
        if(nums.size()==1)return target==nums[0]?true:false;
        int left=0,right=nums.size()-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(nums[mid]==target||nums[left]==target||nums[right]==target)return true;
            if(nums[mid]>nums[right]){
                if(nums[0]<=target&&target<nums[mid])right=mid-1;
                else left=mid+1;
            }
            else if(nums[mid]<nums[left]){
                if(nums[mid]<target&&target<=nums[nums.size()-1])left=mid+1;
                else right=mid-1;
            }
            else {
                if(nums[mid]<target)right--;
                else left++;
            }
        }
        return false;
    }