[Leetcode/C++] 35_Search Insert Position

오늘 학교 알고리즘 수업에서 Binary Search 진도가 나갔는데

Biary Search 복습 및 공부 겸 리트코드의 이진탐색 문제를 찾아 풀어보았습니다.

문제는 다음과 같습니다.

시간복잡도는 O(logn)을 만족해야 하고,
탐색을 하되, 없는 경우 정렬에 맞게 넣어야 할 인덱스 값을 반환해주어야 합니다.

이 없는 경우에 대해서만 잘 처리해주면 될 것 같습니다.

없는 경우에 대한 코드의 처리는 다음과 같습니다.

if(l>=r && v[l]!=t){ // 찾는 값이 없는 경우
    if(v[l]<t) res=l+1;
    else res=l;
            
    return;
}

제 코드는 다음과 같습니다.

class Solution {
public:
    int res, t;
    vector<int> v;
    
    void binarySearch(int l, int r){
        if(l>=r && v[l]!=t){ // 찾는 값이 없는 경우
            if(v[l]<t) res=l+1;
            else res=l;
            return;
        }
        
        int mid = (l+r)/2;
        if(v[mid]==t) res=mid;
        else if(v[mid]<t) binarySearch(mid+1, r);
        else binarySearch(l, mid-1);
        
        return;
    }
    
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        v = nums, t = target;
        
        binarySearch(0, n-1);
        return res;
    }
};