```
class Solution:
def search(self, A, target):
def get(start, end):
if start > end:
return -1
mid = (start+end)/2
if A[mid] == target:
return mid
elif A[mid] >= A[start]: # First half is sorted
if target >= A[start] and target < A[mid]:
return get(start, mid-1)
else:
return get(mid+1, end)
elif A[mid] <= A[end]: # Second half is sorted
if target > A[mid] and target <= A[end]:
return get(mid+1, end)
else:
return get(start, mid-1)
return get(0, len(A)-1)
```