Search Insert Position

문제에서 대놓고 시간 복잡도를 O(log n)으로 제한하고 있다. 이진 탐색을 써야겠다.

이진 탐색 문제와 다른 점은 찾는 것이 없다면 -1을 반환하는 것이 아닌,

찾으면 해당 위치를 반환하고 없으면 삽입할 위치를 반환해야 한다.

내 풀이는 다음과 같다.

1. 이진 탐색을 수행한다.

2. center값과 target을 비교한다.

2-1.target이 크다면 center+1위치의 값과 비교한다. 작다면 두 수 사이에 넣으면 되므로,

   center+1을 반환한다. center+1 보다도 크면 left값을 center+1로 하여 탐색 범위를 좁혀 다시 탐색한다.

2-2. target이 작다면 탐색 범위를 좁혀 다시 루프를 돈다.

2-3. 만약 일치하는 값이 존재한다면 해당 위치를 반환한다.

(2-2) 단계에서 target보다 작은 녀석이 없다면? 이라는 물음이 생길수도 있는데, target이 가장 작거나 큰 경우는 위에서 예외처리로 걸러냈으므로 항상 target보다 작은 녀석이 존재하게 되므로 OK다.

5ms, 9.5MB 사용. 시간은 백분율 20% 메모리는 90%이다.  4ms가 나오면 98%보다 빠르다고 하는데, 돌릴 때마다 4 5 6 7 8 다르게 나오는거 보면 다들 고만고만한 수준인거 같다. 그래서 더이상 최적화는 하지 않았음.

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        //예외처리
        //nums가 비어있을 경우
        if (nums.size() == 0) return 0;
        //nums의 최소값 보다 작은 경우
        if (target < nums[0]) return 0;
        //리스트 내의 모든 수보다 클 경우
        if (target > nums[nums.size() - 1]) return nums.size();
        //이진 탐색을 위한 변수 설정
        int left = 0, right = nums.size() - 1, center = (left + right) / 2;

        while (true)
        {
            //이진 탐색 수행
            //전략: center와 center+1 idx로 하여 target과 계속 비교해 나간다.
            //center와 center+1  사이에 target이 들어올 경우 center+1을 idx로 반환해준다.
            if (target > nums[center])
            {
                //center+1 보다는 작은지 확인
                if (target < nums[center + 1])
                    return center + 1;

                //작지 않다면 탐색 범위를 좁혀 center를 변경한다
                left = center + 1;
                center = (left + right) / 2;
            }
            else if (target < nums[center])
            {
                //탐색 범위를 좁힌다
                right = center - 1;
                center = (left + right) / 2;
            }
            else
            {
                //일치하는 값이 있다면 해당 위치를 반환한다.
                return center;
            }
        }

    }
};