class Solution {
public:
    int search(vector<int>& nums, int target) {

        int n = (int)nums.size();
         if(n == 0) return -1;
        // find the smallest number.

        int l = 0, h = n-1;

        while( l < h )
        {
            int mid = (l + ( h -l )/2);
            if(nums[mid] >nums[h]) l = mid + 1;
            else h = mid;
        }
         //cout<<l<<" "<<h<<"\n";
        // faltten the array and use usual binary search.
       int root = l;
        l=0, h=n-1;

        while(l <= h)
        {
            int mid = (l + (h - l)/2);
           int midr = mid + root;
            midr = midr % n;

            if(nums[midr] == target) return midr;
            if(nums[midr] > target) h = mid - 1;
            else l = mid + 1;
        }

        return -1;

    }
};