```
class Solution {
public:
int bs(const vector<int> &nums,int target,int left,int right) {
if(left>=right)
{
if(nums[right]!=target) return -1;
return right;
}
int mid=(left+right)/2;
if(target==nums[mid])return mid;
// right side is ordered and target is on the right side
if(nums[mid]<target && target<=nums[right]) return bs(nums,target,mid+1,right);
// left side is ordered and target is on the left side
if(nums[left]<=target && target<nums[mid]) return bs(nums,target,left,mid);\
// right side is ordered and target is NOT on the right side
if(nums[mid]<nums[right]) return bs(nums,target,left,mid);
// left side is ordered and target is NOT on the left side
return bs(nums,target,mid+1,right);
}
int search(vector<int>& nums, int target) {
if(nums.size()<1)return -1;
return bs(nums,target,0,nums.size()-1);
}
};
```