```
class Solution(object):
def search(self, nums, target, low=None, high=None):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if low > high:
return - 1
if low is None:
low = 0
high = len(nums) - 1
middle = (low + high)/2
if nums[middle] == target:
return middle
elif low != high:
if nums[middle] <= nums[high]:
if nums[middle] < target <= nums[high]:
return self.search(nums, target, middle + 1, high)
else:
return self.search(nums, target, low, middle - 1)
else:
if nums[low] <= target < nums[middle]:
return self.search(nums, target, low, middle - 1)
else:
return self.search(nums, target, middle + 1, high)
return -1
```