33、Search in Rotated Sorted Arra

这是我在面快手时的一道题目，印象深刻，当时想的把自己绕住了，后来看到答案，才发现实际很简单，不管怎么旋转，总有一半是有序的。

思路
具体来说，假设数组是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;  
  }  
}