[LeetCode] 34. Find First and Last Position of Element in Sorted Array (C++)

문제

오름차순으로 정렬된 정수 배열이 주어질 때 target의 시작과 끝을 찾기

시간복잡도 O(log n)

생각할 것

1. target 숫자 중 가장 작은 인덱스를 찾는 함수 만들기
2. target + 1 숫자에서 인덱스를 하나 뺀 값이 end에 해당

코드

class Solution {
public:
    int findLowerBound(vector<int>& nums, int target) {
        int start = 0, end = nums.size() - 1;
        while(start <= end) {
            int mid = (start + end) / 2;
            if(nums[mid] < target) {
                start = mid + 1;
            }
            else {
                end = mid - 1;
            }
        }
        return start;
    }

    vector<int> searchRange(vector<int>& nums, int target) {
        int start = findLowerBound(nums, target);
        int end = findLowerBound(nums, target + 1) - 1;

        if(start < nums.size() && 0 <= end && nums[start] == target && nums[end] == target) return {start, end};
        else return {-1, -1};
    }
};