rotated_bsearch.cc

class Solution {
public:
    int search(int A[], int n, int target) {
        return bsearch(A, 0, n - 1, target);
    }
    
    int bsearch(int A[], int l, int u, int target) {
        if (l > u) {
            return -1;
        }
        
        int m = (l + u) >> 1;
        if (A[m] == target) {
            return m;
        }
        
        if (A[m] < target) {
            if (A[u] >= A[m] && A[u] < target) {
                return bsearch(A, l, m - 1, target);
            } else {
                return bsearch(A, m + 1, u, target);
            }
        }
        
        if (A[m] > target) {
            if (A[l] <= A[m] && A[l] > target) {
                return bsearch(A, m + 1, u, target);
            } else {
                return bsearch(A, l, m - 1, target);
            }
        }
    }
};