Description

Submission

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

        int mid = (low + high) / 2;
        if(nums[mid] == target) return mid;
        if(nums[low] < nums[mid]) {
            if(target < nums[mid] && target >= nums[low]) return searchUtil(nums, low, mid - 1, target);
            return searchUtil(nums, mid, high, target);
        }

        if(target > nums[mid] && target <= nums[high]) return searchUtil(nums, mid + 1, high, target);
        return searchUtil(nums, low, mid, target);
    }
};