[C++] LeetCode (릿코드) 35 : Search Insert Position

문제

Loading Question... - LeetCode

Search Insert Position - LeetCode

코드

class Solution
{
    public:
        int searchInsert(vector<int> &nums, int target)
        {
            int lo = 0;
            int hi = nums.size() - 1;
            int res = nums.size();

            while (lo <= hi)
            {
                int md = (lo + hi) / 2;
                if (nums[md] < target)
                {
                    lo = md + 1;
                }
                else
                {
                    res = md;
                    hi = md - 1;
                }
            }
            return res;
        }
};

설명

오름차순으로 정렬된 벡터와 한 숫자가 주어졌을 때, 오름차순 정렬을 유지하면서 그 숫자를 삽입할 최초의 위치를 찾는 문제이다.

중간 지점이 target보다 작으면 삽입할 수 없기 때문에 왼쪽의 범위를 배제한다.
target보다 크거나 같으면 삽입할 수 있기 때문에 오른쪽 범위를 배제하고 그 인덱스를 저장한다.
반복하면 res에 삽입할 수 있는 최초의 위치가 저장된다.

단, 벡터에 있는 모든 수가 target보다 작을 경우 res는 초깃값에서 변동되지 않기 때문에
res의 초깃값을 마지막 위치로 설정해야 한다.