class Solution {
public:
    int search(vector<int>& nums, int target) {
        int len_n = nums.size();
        int lo = 0, hi = len_n-1;
        int mid, s_ind;
        while(lo<hi)
        {
            mid = (lo+hi)/2;
            if(nums[mid]>nums[hi]){
                lo = mid+1;
            }
            else
                hi = mid;
        }
        s_ind = lo;

        lo = 0, hi = len_n - 1;
        while(lo<=hi){
            mid = (lo + hi)/2;
            int realmid = (mid + s_ind)%len_n;
            if(nums[realmid] == target)
                return realmid;
            if(nums[realmid]>target){
                hi = mid-1;
            }
            else if(nums[realmid]<target)
                lo = mid+1;
        }
        return -1;

    }
};