class Solution {
public:
    int search(vector<int>& nums, int target) {
        for(int i=0 ; i<nums.size() ;i++)
            if(nums[i] == target) return i;
        return -1;
    }
};

class Solution {
public:
    int find(vector<int>& nums, int target , int left ,int right)
    {
        if(left > right) return -1;
        if(nums[right] > nums[left] && nums[left] > target) return -1;
        else if(nums[right] > nums[left] && nums[right] < target) return -1;
        if(left == right && nums[left] == target) return left;
        else if(left == right && nums[left] != target) return -1;
        int mid = (left+right)/2;
        if(nums[mid] == target) return mid;
        if(left < right)
        {
            int left_value = find(nums,target,left,mid-1);
            int right_value = find(nums,target,mid+1,right);
            if(left_value != -1) return left_value;
            if(right_value != -1) return right_value;
        }
        return -1;
    }
    int search(vector<int>& nums, int target) {
        return find(nums,target,0,nums.size()-1);
    }
};