Search in a Rotated Array

Given a sorted and rotated array A of N distinct elements which is rotated at some point, and given an element key. The task is to find the index of the given element key in the array A.

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

class Solution{
public:
    int search(int A[], int low, int high, int key){
        int mi = -1, n = high;
        int l = 0, r = n - 1;
        while(l < r) {
            int m = l + (r - l) / 2;
            if(A[m] < A[r]) r = m;
            else l = m + 1;
        }
        mi = r;
        
        l = 0, r = n - 1;
        while(l <= r) {
            int m = l + (r - l) / 2;
            if(A[(m + mi) % n] == key) return (m + mi) % n;
            
            if(A[(m + mi) % n] > key) r = m - 1;
            else l = m + 1;
        }
        return -1;
    }
};