class Solution {
public:
    // 二分查找，然后向左向右扩展，找到第一次出现和最后一次出现
    vector<int> searchRange(vector<int>& nums, int target) {
        int ans = -1, left = 0, right = nums.size() - 1, mid = (left + right) / 2;
        if (right < 0) return {-1, -1};
        if (nums[left] == nums[right] && nums[left] == target)
            return {left, right};
        while (left <= right) {
            if (nums[mid] == target) {
                ans = mid;
                break;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
            mid = (left + right) / 2;
        }
        if (ans == -1) return {-1, -1};
        int firstAns = ans, lastAns = ans;
        while (firstAns > 0) {
            if (nums[firstAns - 1] != nums[ans])
                break;
            firstAns--;
        }
        while (lastAns < nums.size() - 1) {
            if (nums[lastAns + 1] != nums[ans])
                break;
            lastAns++;
        }
        return {firstAns, lastAns};
    }
};