LeetCode (C/C++) 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/

---

풀이

O(log n) 의 시간복잡도 + 정렬된 배열이라 이분탐색으로 풀어야겠다는 생각이 들었다.
이분탐색 후 찾은 target의 인덱스부터 앞 뒤로 탐색하며 target의 범위를 찾는다.

---

코드

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        // 주어진 배열이 비었을 때
        if (nums.empty()) 
            return {-1, -1};

        // 이분탐색
        int start = 0, mid, end = nums.size() - 1;
        while (start <= end) {
            mid = (start + end) / 2;

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

        // 찾는 값이 없을 때
        if (nums[mid] != target)
            return {-1, -1};

        // 찾은 값의 처음, 마지막 인덱스 찾기
        start = end = mid;
        while (0 <= start && nums[start] == target)
            start--;

        while (end < nums.size() && nums[end] == target)
            end++;

        return {start + 1, end - 1};
    }
};