[Leetcode] 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/

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

문제 내용

정렬된 배열에서 target 숫자가 중복되서 반복되는데

첫번째 index와 마지막 index를 출력하는 문제

 

Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

 

문제 풀이

binary search 로 log(n) 만에 풀 수 있다.

lower bound로 첫번째 index를 구하고

upper bound로 마지막 index를 구한다.

 

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        auto s = lower_bound(nums.begin(), nums.end(), target);
        if (s == nums.end() || *s != target)
            return {-1, -1};
        auto e = upper_bound(nums.begin(), nums.end(), target);
        return {(int)(s-nums.begin()), (int)(e-nums.begin()-1)};
    }
};