This solution is based on the basic Binary Search. We only need to consider two added situations that are generated by rotation.

```
class Solution {
public:
int search(int A[], int n, int target) {
return helper(0,n-1,A,target);
}
//Basic Binary Search with considering two added situations because of rotation.
int helper(int start, int end, int A[], int target){
int mid=(start+end)/2;
if(A[mid]==target) return mid;
if(start>=end) return -1;
if(target<A[mid]){
//consider the situation when part of the values that less than A[mid] was rotated to the right.
if(A[mid]>A[end]&&target<A[start]) return helper(mid+1, end, A, target);
else return helper(start, mid-1, A, target);
}
else{
//consider the situation when part of the values that larger than A[mid] was rotated to the left.
if(A[mid]<A[start]&&target>A[end]) return helper(start, mid-1, A, target);
else return helper(mid+1, end, A, target);
}
}
};
```