Find First and Last Position of Element in Sorted Array

問題の説明

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>

コード#コード#

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함수에서 존재하지않는 값에 접근하는 오버플로우의 발생에 조심해야한다.