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

문제에서 O(log n) 이라고 했으니 이진탐색으로 풀어야 한다.

가장 작은 idx와 가장 큰 idx 를 골라내어야 한다.

가장 작은 경우: mid값이 target보다 크거나 같다면 right를 mid-1로 지정하고, 아니라면 left를 mid+1로 지정한다. 이 이유는 같은 경우에도 왼쪽에 더 작은 값이 있는지 봐야하기 때문이다.

가장 큰 경우: mid값이 target보다 크다면 right를 mid-1로 지정하고, 아니라면 left를 mid+1로 지정한다. 이유는 left right가 겹칠때까지 전부 찾은다음 target의 가장 큰 idx를 찾아야 하기 때문이다.

if문에서 같으면 무조건 갱신하는 것 또한 중요하다.

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> result(2, -1);
        
        int size = nums.size(), left = 0, right = size-1, ans = -1;
        //get min
        while(left <= right)
        {
            int mid = (right+left)/2;
            if(nums[mid] == target)
                ans = mid;
            nums[mid] >= target? right = mid - 1 : left = mid + 1;
        }
        result[0] = ans;
        
        //resetting
        left = 0, right = size-1, ans = -1;

        //get max
        //가운데값이 크면은 오른쪽을 줄인다. 같다면 왼쪽을 줄여서 더 오른쪽에도 같은 값이 있는지 확인한다.
        while(left<= right)
        {
            int mid = (left+right)/2;
            
            if(nums[mid] == target)
                ans = mid;
            nums[mid] > target ? right = mid -1 : left = mid + 1;
        }

        result[1] = ans;
        return result;
    }
};