The idea is basic binary search with some tricky points to think of.

Since the array is rotated, we have to make sure which part we are in right now. The order is ascending order, so we compare with the right one to decide.

Two cases:

A1= [4,5,6,7,8,9,1,2,3];

A2= [9,1,2,3,4,5,6,7,8];

In A1, l=4, r=3, m=8, A[m]>A[r], we can know A[l] to A[m] is in ascending order.

In A2, l=9, r=8, m=4, A[r]>A[m], we can know A[m] to A[r] is in ascending order.

After this, we compare the target with the two boundary elements of the ascending ordered part, see if the target lie in it. If not so, we choose from the other part.

Note that in BST, if we give `while(left<=right)`

, we have to make sure, `right=mid-1`

, and `left=mid+1`

, so that every element will be reached.

```
public class Solution {
public int search(int[] A, int target) {
if(A==null || A.length==0)
return -1;
int l = 0;
int r = A.length-1;
while(l<=r)
{
int m = (l+r)/2;
if(target == A[m])
return m;
if(A[m]<A[r]){
if(target>A[m] && target<=A[r])
l = m+1;
else
r = m-1;
}
else{
if(target>=A[l] && target<A[m])
r = m-1;
else
l = m+1;
}
}
return -1;
}
}
```

Get the idea from here.