Find First and Last Position of Element in Sorted Array

유승선 ·2024년 2월 9일
0

LeetCode

목록 보기
101/121

내 테마에 조금 어긋나긴하지만 그래도 바이너리 서치 문제를 한번 풀어봤는데 재밌었다. target 이 주어졌을때 가장 첫번째 위치와 가장 마지막 위치를 return 하면 되는 문제다.

만약에 없으면 -1,-1을 리턴하면 된다. 이 문제에서 가장 먼저 첫번쨰 target 을 바이너리 서치로 찾아봤고 가장 먼저 나온 구간을 탐색하기 위해서 target 을 찾았어도 end 구간을 줄여줬다.

가장 마지막에 나온 구간을 탐색하기 위해서는 left 구간을 늘려줬다.

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> answer(2,-1); 

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

        while(start <= end){
            int mid = start + (end - start) / 2;
            
            if(nums[mid] == target){
                answer[0] = mid; 
                end = mid - 1; 
            }

            else if(nums[mid] < target) start = mid + 1;
            else end = mid - 1; 
        }

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

        while(start <= end){
            int mid = start + (end - start) / 2; 

            if(nums[mid] == target){
                answer[1] = mid; 
                start = mid + 1; 
            }

            else if(nums[mid] < target) start = mid + 1; 
            else end = mid - 1; 
        }


        return answer; 
    }
};
profile
성장하는 사람

0개의 댓글