class Solution {
    /** 
     * param A : an integer ratated sorted array
     * param target :  an integer to be searched
     * return : an integer
     */
public:
    int search(vector<int> &A, int target) {
        // write your code here
        int size = A.size();
        if (size == 0) {
            return -1;
        }

        int start = 0;
        int end = size - 1;

        // 先讨论A[mid]落在前一半还是后一半，通过讨论A[mid]和A[end]的大小关系来确定；再确定A[mid]的位置后，讨论target是落在A[mid]的左边还是右边
        while (start + 1 < end) {
            int mid = (end - start) / 2 + start;
            if (A[mid] == target) {
                return mid;
            } else if (A[start] < A[mid]) {
                if(target >= A[start] && target <= A[mid]) {
                    end = mid;
                } else {
                    start = mid;
                }
            } else {
                if (target <= A[end] && target >= A[mid]) {
                    start = mid;
                } else {
                    end = mid;
                }
            }
        }
        if (A[start] == target) {
            return start;
        }

        if (A[end] == target) {
            return end;
        }

        return -1;
    }
};