Find First and Last Position of Element in Sorted Array C++

백준만 풀다가 내년부터는 리트코드를 쭉 풀어보려고 한다.(이유는 Discuss 탭의 다양하고 알찬 정보들 보기)

Discuss에서 시간 복잡도나, 다른 사람의 생각을 볼 수 있다는 게 큰 장점인 것 같기도 하다.

 

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/?envType=study-plan&id=algorithm-ii 

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

이분 탐색 문제에서 lower_bound,upper_bound를 이용해 해결했다.

 [5,7,7,8,8,10], target = 8

일떄, target의 시작과 target의 마지막 인덱스를 찾는 문제이다.

 

 

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> ans;
        if(nums.size() == 0 || (nums[nums.size()-1] < target)){
            ans.push_back(-1);
            ans.push_back(-1);
            return ans;
        }
        
        int firstIndex = lower_bound(nums.begin(),nums.end(),target) - nums.begin();
        if(nums[firstIndex] != target){
            ans.push_back(-1);
            ans.push_back(-1);
        }
        else{
            ans.push_back(firstIndex);
            int lastIndex = upper_bound(nums.begin(),nums.end(),target) - nums.begin();
            lastIndex -= 1;
            ans.push_back(lastIndex);
        }
        return ans;
    
    }
};