这是我在面快手时的一道题目，印象深刻，当时想的把自己绕住了，后来看到答案，才发现实际很简单，不管怎么旋转，总有一半是有序的。
思路
具体来说，假设数组是A，每次左边缘为l，右边缘为r，还有中间位置是m。在每次迭代中，分三种情况：
（1）如果target==A[m]，那么m就是我们要的结果，直接返回；
（2）如果A[m]<A[r]，那么说明从m到r一定是有序的（没有受到rotate的影响），那么我们只需要判断target是不是在m到r之间，如果是则把左边缘移到m+1，否则就target在另一半，即把右边缘移到m-1。
（3）如果A[m]>=A[r]，那么说明从l到m一定是有序的，同样只需要判断target是否在这个范围内，相应的移动边缘即可。
解法
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;
}
}
