public class Solution {

```
public int search(int[] nums, int target) {
if (nums == null || nums.length == 0) return -1;
return search(nums, 0, nums.length-1, target);
}
public int search(int[] nums, int fromIndex, int toIndex, int target) {
int currentIndex = (fromIndex + toIndex) >> 1;
if (fromIndex == currentIndex) {
if (nums[currentIndex] == target) return currentIndex;
if (nums[toIndex] == target) return toIndex;
return -1;
}
int from = nums[fromIndex];
int to = nums[toIndex];
if (from < to) {
int current = nums[currentIndex];
if (current <= target)
return search(nums, currentIndex, toIndex, target);
else
return search(nums, fromIndex, currentIndex - 1, target);
} else {
int i1 = search(nums, fromIndex, currentIndex-1, target);
int i2 = search(nums, currentIndex, toIndex, target);
if (i1 != -1)
return i1;
else if (i2 != -1)
return i2;
else
return -1;
}
}
```

}