33

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int k = findK(nums);
        if(k == nums.size()) k = 0;

        // Search left sorted side.
        int idx = lower_bound(nums.begin(), nums.begin()+k, target)-nums.begin();
        if(idx < nums.size() && nums[idx] == target)
            return idx;

        // Search right sorted side.
        idx = lower_bound(nums.begin()+k, nums.end(), target) - nums.begin();
        if(idx < nums.size() && nums[idx] == target)
            return idx;

        // Number not found.
        return -1;
    }

    int findK(vector<int> &nums){
        int l=0, r=nums.size();
        while(l<r){
            int mid = (l+r)/2;
            if(nums[mid] < nums[0])
                r = mid;
            else
                l = mid+1;
        }
        return l;
    }

};