81. Search in Rotated Sorted Array II

There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).

Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]] (0-indexed). For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].

Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        for(auto& num : nums)
            if(num == target)
                return true;
        return false;
    }
};

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        if(nums.size() == 1)
            return nums[0] == target;
        if(nums[0] == target)
            return true;
        for(int i = 1; i < nums.size(); i++) {
            if(nums[i] < nums[i - 1]) {
                if(nums[0] < target)
                    return false;
                auto it = lower_bound(nums.begin() + i, nums.end(), target);
                return it != end(nums) && *it == target;
            } else if(nums[i] == target)
                return true;
        }
        return false;
    }
};

class Solution {
    bool recursiveBinarySearch(vector<int>& nums, int start, int end, int target) {
        if(start + 1 >= end)
            return nums[start] == target || nums[end] == target;
        int mid = (start + end)>>1;
        if(nums[start] < nums[mid] && nums[start] <= target && target <= nums[mid])
            return *lower_bound(nums.begin() + start, nums.begin() + mid, target) == target;
        if(nums[mid + 1] < nums[end] && nums[mid + 1] <= target && target <= nums[end])
            return *lower_bound(nums.begin() + mid + 1, nums.begin() + end, target) == target;
        if(nums[start] < nums[mid] && nums[mid] < target)
            return recursiveBinarySearch(nums, mid + 1, end, target);

        return recursiveBinarySearch(nums, start, mid, target) || recursiveBinarySearch(nums, mid + 1, end, target);


    }
public:
    bool search(vector<int>& nums, int target) {
        return recursiveBinarySearch(nums, 0, nums.size() - 1, target);
    }
};