정렬된 정수 배열 nums와 목표값 target이 주어졌을 때, 이 목표값이 처음 나타나는 위치와 마지막으로 나타나는 위치를 반환하는 문제입니다. 만약 목표값이 존재하지 않으면 [-1, -1]을 반환해야 하며, 알고리즘은 반드시 O(log n) 시간 복잡도를 가져야 합니다.

예시:

입력: nums = [5,7,7,8,8,10], target = 8
출력: [3,4]

초기 시도에서는 모든 일치하는 인덱스를 set에 저장하는 방식으로 구현했지만, 이는 중복 탐색과 불필요한 데이터 구조 사용으로 인해 시간 복잡도가 높아져 제약 조건을 만족하지 못했습니다.

올바른 접근법은 두 번의 이분 탐색을 통해 각각 시작 위치와 끝 위치를 찾는 것입니다. 첫 번째 이분 탐색은 왼쪽 경계(최소 인덱스)를, 두 번째는 오른쪽 경계(최대 인덱스)를 찾습니다. 이 방법은 단일 이분 탐색만으로는 한쪽 경계만 확정할 수 있다는 점에서 유용합니다.

왼쪽 경계를 찾을 때는, nums[mid] == target인 경우에도 왼쪽에 더 작은 값이 있는지 확인하기 위해 r = mid - 1로 이동하며, nums[mid-1] != target이면 현재 mid가 최초 등장 위치임을 의미합니다. 반대로 오른쪽 경계는 nums[mid+1] != target이면 현재 mid가 마지막 등장 위치입니다.

다음은 개선된 구현 예시입니다:

vector<int> searchRange(vector<int>& nums, int target) {
    if (nums.empty()) return {-1, -1};

    vector<int> result{-1, -1};
    int left = 0, right = nums.size() - 1;

    // 왼쪽 경계 찾기
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target && (mid == 0 || nums[mid - 1] != target)) {
            result[0] = mid;
            break;
        } else if (nums[mid] >= target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    // 오른쪽 경계 찾기
    left = 0;
    right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target && (mid == nums.size() - 1 || nums[mid + 1] != target)) {
            result[1] = mid;
            break;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return result;
}

이 코드는 두 번의 독립적인 이분 탐색을 수행하며, 각각 최소 및 최대 인덱스를 정확히 찾아냅니다. 특히 mid가 목표값과 같을 때, 그 전/후 요소를 비교하여 경계 조건을 판단함으로써 정확한 범위를 추출할 수 있습니다.