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