LeetCode : 34. Find First and Last Position of Element in Sorted Array

이분탐색 문제이다.

 

[메인 로직]

low, high값을 잡고 mid가 target과 같을 때, 작을 때, 클 때를 나누어서 구현하면 된다.

같을 때 -> 위, 아래로 같은 값이 나오면 탐색한다.

작을 때 -> 정렬된 상태이기 때문에 low = mid+1;

클 때 - > high = mid-1;

 

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int low = 0;
        int high = nums.size()-1;
        int Start = 0, End = 0;
        vector<int> ans;
        bool check = false;
        
        if(nums.size()==1){
            if(nums[0]==target){
                check = true;
            }
        }
        
        while(low<=high){
            int mid = (low+high)/2;
            if(nums[mid]==target){
                check = true;
                Start = mid, End = mid;
                while(End<nums.size()-1 && nums[End]==nums[End+1]){
                    End++;
                }
                while(Start>0 && nums[Start]==nums[Start-1]){
                    Start--;
                }
                break;
            }else if(nums[mid]>target){
                high = mid-1;
            }else{
                low = mid+1;
            }
        }
        
        if(check==true){
            ans.push_back(Start);
            ans.push_back(End);            
        }else{
            ans.push_back(-1);
            ans.push_back(-1);
        }
 
        return ans;
    }
};