Find First and Last Position of Element in Sorted Array

Find First and Last Position of Element in Sorted Array

문제설명

1. 정렬된 정수배열 nums의 값 중에서 target과 같은 값의 시작 인덱스와 끝 인덱스 리턴

2. 없다면 [-1, -1] 리턴

3. O(log n)의 시간복잡도를 갖게 하여라.

4. 제한사항

   0 <= nums.length <= 105
   -109 <= nums[i] <= 109
   nums is a non-decreasing array.
   -109 <= target <= 109

문제해결과정

Input 	: vector<int> nums, int target
Output 	: vector<int>

이분탐색으로 target을 찾은 뒤 앞뒤로 하여 target과 다른 수가 나올 때 까지 인덱스값을 바꿔가며 시작,끝 인덱스를 찾아 리턴

코드

[2020.11.22]

class Solution {
public:
	// target을 발견했을 때 시작인덱스와 끝인덱스를 찾는 함수
    vector<int> find(vector<int>& nums, int mid, int target) {
        int start = mid, end = mid;
        while(nums[start] == target) {
            if(start - 1 >= 0) start--;
            else  {
                start--;
                break;
            }
        } 
        while(nums[end] == target) {
            if(end + 1 < nums.size()) end++;
            else {
                end++;
                break;
            }
        }  
        return {start+1, end-1};
    }
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> answer = {-1, -1};
        
        if(nums.size() == 0) return answer;
        
        int first = 0, last = nums.size() -1, mid = (first+last)/2;
        while(1) {
            if(nums[mid] < target) {
                first = mid;
                mid = (first+last)/2;
            }
            else if(nums[mid] > target) {
                last = mid;
                mid = (first+last)/2;
            }
            else {
                return find(nums, mid, target);
                break;
            }
            if(first == last || first + 1 == last) {
                if(nums[first] == target) return find(nums, first, target);
                else if(nums[last] == target) return find(nums, last, target);
                break;
            }
        }
        return answer;
    }
};

# 예외케이스
	
    first와 last의 값이 같을 때와 나란히 존재할때에 끝내주지 않으면 런타임에러(무한루프)가 나오기에 break문을 설정해줘야한다.
    이때 두 값 중에 답이 존재할 수 있기에 확인한다.
    
# 주의
	
    find함수에서 존재하지않는 값에 접근하는 오버플로우의 발생에 조심해야한다.