class Solution {
private:
    bool bs(const vector<int>& nums, int l, int r, int target) {
        while (l < r) {
            const int mid = (l + r) >> 1;
            if (nums[mid] >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }

        return nums[r] == target;
    }

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

        while (n && nums[n] == nums[0]) {
            --n;
        }

        if (nums[n] >= nums[0]) {
            return bs(nums, 0, n, target);
        }

        int l = 0, r = n;
        while (l < r) {
            const int mid = (l + r) >> 1;
            if (nums[mid] < nums[0]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }

        if (nums[0] > target) {
            return bs(nums, r, n, target);
        }
        return bs(nums, 0, r - 1, target);
    }
};