34. Find First and Last Position of Element in Sorted Array

문제 설명

감소하지 않는 정수형 배열 nums가 주어지면, target 값의 시작과 끝 위치를 찾으시오.
만약 target 값을 찾을 수 없다면, [-1,-1]을 반환한다.
반드시 O(logn)의 시간복잡도로 작성하여라.

출력 예시

접근 방법

첫번째 시도

시간 복잡도 제한을 보고 이분 탐색으로 접근했다.
처음에는 binary search 함수를 새로 작성해서 짜다가, 단순히 인덱스 값만 변화하는 게 더 효율적이지 않나,,, 해서 while문 내부에서 이분 탐색 실시

소스코드

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int result=-1;
        int start=0;
        int end=nums.size()-1;
        while(start <= end){
            int mid = (start + end)/2;
            if(nums[mid]> target){
                end = mid-1;
            }
            else if(nums[mid] < target){
                start = mid+1;
            }
            else {
               result = mid;
               break;
            }
        }

        int first,second;

        if(result<0) return {-1,-1};
        else {
            for(int i=result; i>=0; i--) {
                if(nums[i]!=target) break;
                else first = i;
            }
            
            for(int j=result; j<nums.size(); j++) {
                if(nums[j]!=target) break;
                else second = j;
            }

            return {first,second};
        }
    }
};

돌아보기