在转动过的有序数组中寻找目标值

class Solution {
public:
    int search(int A[], int n, int target) {
        for(int i=0;i<n;i++)
            if(A[i]==target)
                return i;
         return -1;
    }
};

class Solution {
public:
    int search(int A[], int n, int target) {
        int first=0;
        int last=n-1;
        while(first<=last)
        {
            int mid=first+(last-first)/2;
            if(A[mid]==target) 
                return mid;
            
            if(A[first]<=A[mid])//左边有序
            {
                if(A[first]<=target&&target<A[mid])
                    last=mid-1;
                else
                    first=mid+1;
            }
            else//右边有序
            {
                 if(A[mid]<target&&target<=A[last])
                     first=mid+1;
                 else
                     last=mid-1;
                    
            }
        }
        
        return -1;
        
    }
};