Description

Submission

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

private:
    bool partialSearch(vector<int>& nums, int target, int l, int r) {
        if(r - l == 1) {
            return (target == nums[l]) || (target == nums[r]);
        }
        int m = (l + r) / 2;

        if(nums[m] == target) return true;
        if(l >= r) return false;
        if(nums[m] < nums[r])
            return binarySearch(nums, target, m + 1, r) ||
                partialSearch(nums, target, l, m - 1);
        if(nums[l] < nums[m])
            return binarySearch(nums, target, l, m - 1) ||
                partialSearch(nums, target, m + 1, r);

        return false;
    }

    bool binarySearch(vector<int>& nums, int target, int l, int r) {
        int m = (l + r) / 2;
        if(target == nums[m]) return true;
        if(l >= r) return false;
        if(target < nums[m]) return binarySearch(nums, target, l, m - 1);
        if(target > nums[m]) return binarySearch(nums, target, m + 1, r);
        return false;
    }
};