[Binary Search][Medium] 34. Find First and Last Position of Element in Sorted Array

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/description

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

 

Q. 주어진 정렬된 배열 nums에서 target이 존재하면, 그 시작과 끝 index를 찾아라. 

 nums배열에는 중복된 값이 존재 할 수 있다. 

 target이 없다면 각각 -1을 반환하라.

 

Solution. 

 만족조건 - 이 문제에서는 2개의 만족 조건을 찾는다. 

   1) 가장 작은 위치의 target 찾기. - target을 먼저 찾고, 왼쪽값도 target과 같은지 확인한다. 같다면 왼편으로 다시 진행, 다르다면 현재 위치(mid)가 첫 시작 위치가 된다.  

   2) 가장 큰 위치의 target 찾기.  - target 을 먼저 찾고, 오른쪽 값을 비교한다. target과 같다면 오른쪽으로 다시 진행, 다르다면 현재 위치가 가장 큰 마지막 위치가 된다. 

 

 진행조건

   목표값을 찾는다. 

   정렬된 배열이므로, target보다 mid 값이 작다면 오른쪽, 크다면 왼쪽으로 검색해 나간다. 

 

 예외처리 

    현재 위치(mid)를 좌, 우의 값과 비교할때, 전체 배열의 범위를 초과하지 않는지 확인이 필요하다. 

 

 로직대로 코드를 작성한다. 

int searchRangeBS_Start(vector<int>& nums, int target, int left, int right)
    {
        if (left > right)	return -1;

        int mid = left + (right - left) / 2;

        if (nums[mid] < target)
            return searchRangeBS_Start(nums, target, mid + 1, right);
        else if (nums[mid] > target)
            return searchRangeBS_Start(nums, target, left, mid - 1);
        else
        {
            if (mid>0 && nums[mid-1]==nums[mid])
                return searchRangeBS_Start(nums, target, left, mid - 1);
            else
                return mid;
        }
    }
    int searchRangeBS_End(vector<int>& nums, int target, int left, int right)
    {
        if (left > right)	return -1;

        int mid = left + (right - left) / 2;

        if (nums[mid] < target)
            return searchRangeBS_End(nums, target, mid + 1, right);
        else if (nums[mid] > target)
            return searchRangeBS_End(nums, target, left, mid - 1);
        else
        {
            if (mid==nums.size()-1 || (mid<nums.size()-1 && nums[mid+1]!=nums[mid]))
                return mid;
            else
                return searchRangeBS_End(nums, target, mid + 1, right);
        }
    }
public:
    vector<int> searchRange(vector<int>& nums, int target) 
    {
        vector<int> vOut;
        vOut.resize(2, -1);
        vOut[0] = searchRangeBS_Start(nums, target, 0, nums.size() - 1);
        vOut[1] = searchRangeBS_End(nums, target, 0, nums.size() - 1);
        return vOut;
    }

 

적당한 결과를 확인할 수 있다.