LeetCode#29.cc

class Solution {
private:
    int findLeast(int A[], int n){
        int low = 0,high = n-1;
        while(low<=high){
            int mid = (low+high)/2;
            if(A[mid]>A[0] || A[mid] > A[n-1])
                low = mid+1;
            else high = mid-1;
        }
        return low;
    }
    int binarySearch(int A[], int low, int high, int target){
        while(low<=high){
            int mid = (low+high)/2;
            if(A[mid]==target) return mid;
            else if(A[mid] > target) high = mid-1;
            else low = mid+1;
        }
        return -1;
    }
public:
    int search(int A[], int n, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        assert(A!=NULL);
        
        if(n==0) return -1;
        
        if(A[0]==target&&n==1) return 0;
        if(A[0]!=target&&n==1) return -1;
        
        if(A[0]<A[n-1]){
            return binarySearch(A,0,n-1,target);
        }
        else{
            int least = findLeast(A,n);
            int a = binarySearch(A,0,least-1,target);
            int b = binarySearch(A,least,n-1,target);
            if(a!=-1) return a;
            if(b!=-1) return b;
            return  -1;
        }
        
    }
};