[Leetcode,c++] Find First and Last Position of Element in Sorted Array

문제

Find First and Last Position of Element in Sorted Array - LeetCode

 

코드

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {

        int start = 0;
        int end = nums.size()-1;

        int first_index = -1,last_index = -1;
        vector<int>ans;

        while(start<=end){
            int mid = (start+end)/2;
            if(nums[mid]>target) end=mid-1;
            else if(nums[mid]<target) start=mid+1;
            else{
                first_index = last_index = mid;
                break;
            }
        }

        int index = first_index;

        while(--index>=0&&nums[index]==target) first_index--;

        index = last_index;

        while(++index<nums.size()&&nums[index]==target) last_index++;

        ans.emplace_back(first_index);
        ans.emplace_back(last_index);

        if(ans.size()==0||index == -1) return {-1,-1};
        return ans;
    }
};

 

풀이

기본적인 이분 탐색을 통해서 target의 index번호를 일단 먼저 찾습니다. 그 후 그 인덱스 번호를 기점으로 좌 우로 퍼져 나가면서 다른 값이 나올 때까지 찾으면 target의 시작 index와  끝 index를 찾을 수 있습니다.