Rotated Sorted Array Search

• Time : $O(logn)$
• Space : $O(1)$

int helper(const vector<int>& A) {
    int res = A.size() - 1, skip = 1;
    while(res) {
        if(A[res] < A[res - 1]) return res;
        if(res - skip < 0) skip = 1;
        else {
            if(A[res - skip] < A[res]) res -= skip, skip = skip * 2;
            else skip = 1;    
        }
    }
    return res;
}
int Solution::search(const vector<int> &A, int B) {
    int mid = helper(A);
    int l = 0, r = A.size() - 1, n = A.size();
    while(l <= r) {
        int m = l + (r - l) / 2;
        int p = (m + mid) % n;
        if(A[p] == B) return p;
        else if(A[p] < B) l = m + 1;
        else r = m - 1;
    }
    return -1;
}