#include <bits/stdc++.h>

using namespace std;

vector<int> searchRange(vector<int>& nums, int target);
int binarySearchMiddle(vector<int>& nums, int target);
int binarySearchLeft(vector<int>& nums, int target);
int binarySearchRight(vector<int>& nums, int target);

int main(int argc, char const *argv[])
{
    vector<int> nums = {1,2,3,3,3,3,4,5,9};
    vector<int> range = searchRange(nums, 3);
    int left = range[0];
    int right = range[1];
    cout << left << ' ' << right << endl;
    return 0;
}

vector<int> searchRange(vector<int>& nums, int target) {
    int middle = binarySearchMiddle(nums, target);
    if (middle == -1) {
        return vector<int>({-1, -1});
    }

    vector<int> forLeftSearch(nums.begin(), nums.begin() + middle);
    vector<int> forRightSearch(nums.begin() + middle, nums.end());
    int left = binarySearchLeft(forLeftSearch, target);
    int right = binarySearchRight(forRightSearch, target);

    if (left == -1) {
        left = middle;
    }
    if (right == -1) {
        right = middle;
    }

    cout << middle << endl;
    return vector<int>({left, right + middle});
}

int binarySearchMiddle(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;

    if (nums.size() == 0) {
        return -1;
    }

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] == target) {
            return mid;
        }

        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

int binarySearchLeft(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size();

    if (nums.size() == 0) {
        return -1;
    } else if (nums[left] == target) {
         return left;
    }

    while (left < right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] != target && nums[mid + 1] == target) {
            return mid + 1;
        }

        if (nums[mid] < target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    if (nums[left] < nums.size() - 1 && nums[left] != target && nums[left + 1] == target) {
        return left;
    }
    return -1;
}

int binarySearchRight(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size();

    if (nums.size() == 0) {
        return -1;
    } else if (nums[right - 1] == target) {
        return right - 1;
    }

    while (left < right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] != target && nums[mid + 1] == target) {
            return mid + 1;
        }

        if (nums[mid] < target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    if (nums[left] < nums.size() - 1 && nums[left] != target && nums[left + 1] == target) {
        return left;
    }
    return -1;
}