[Leetcode] 35. Search Insert Position (C++)

문제

35. Search Insert Position

코드

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int lo = 0, hi = nums.size()-1;
        
        while (lo < hi){
            int mid = lo + (hi-lo)/2;
            
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) lo = mid+1;
            else hi = mid-1;
        }
        return nums[lo] < target ? lo+1 : lo;
    }
};

접근

입력이 정렬된 배열이고 시간 복잡도 O(log N) 으로 해결하라고 해서 자연스럽게 이진탐색이 떠올랐다. 기본적으로 이진탐색을 따르면서 target이 있는지 찾고, 있다면 그 인덱스를 반환한다. 없다면 들어갈 곳을 찾아야하기 때문에 while 문 이후 그 인덱스 값(lo)과 target 값을 비교해 주는 과정이 필요하다.

추가) mid 값을 구할 때 mid = (lo+hi)/2 가 자연스럽지만 입력 배열의 크기에 따라 (lo+hi) 에서 overflow가 발생할 수 있다. 이를 방지하고자 항상 mid = lo + (hi-lo)/2로 사용하고 있다.