[알고리즘문제] 릿코드 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

 

정렬된 number타입 배열과 number타입 value가 들어온다.

배열에서 value가 존재하는 start index와 end index를 return 한다.

조건은 Time complexity는 O(logn)이 되어야 한다.

#include<iostream>
#include<vector>

using namespace std;

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.size() == 0) return { -1, -1 };

        vector<int> answer = { -1, -1 };
        int start = 0;
        int end = nums.size() - 1;

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

            if (nums[mid] == target) {
                while (nums[start] != target) {
                    start++;
                }
                while (nums[end] != target) {
                    end--;
                }
                answer[0] = start;
                answer[1] = end;
                return answer;
            }
            else if(nums[mid] < target){
                // 하위 idx 탐색
                start = mid + 1;
            }
            else {
                // 상위 idx 탐색
                end = mid - 1;
            }
        }

        return answer;
    }
};