The idea to solve this problem is extremely clear and simple:

- Find the index of the smallest number;
- Split the array into two ordered parts at the index;
- Use
**Arrays.binarySearch(..)**to find the answer.

On the third step, I feel like it is cheating. What's your thought on this?

```
public int search(int[] A, int target) {
if (A == null || A.length == 0) {
return -1;
}
int pivot = indexOfMin(A, 0, A.length - 1);
int resL = Arrays.binarySearch(A, 0, pivot, target);
if (resL >= 0)
return resL;
int resR = Arrays.binarySearch(A, pivot, A.length, target);
if (resR >= 0)
return resR;
return -1;
}
public int indexOfMin(int[] A, int start, int end) {
if (A[start] <= A[end]) {
return start;
}
int mid = (start + end) / 2;
int i = indexOfMin(A, start, mid); // min index of left half
int j = indexOfMin(A, mid + 1, end); // min index of right half
return A[i] < A[j] ? i : j;
}
```