[Binary Search] Search Insert Position

1. 문제

LeetCode - Search Insert Position

• 고유한 정수로 구성된 정렬된 배열 nums가 주어졌을 때
• 정수 target을 찾으면, 해당 인덱스를 반환
• target을 찾지 못했다면, 정렬 순서 상 삽입되어야 할 인덱스를 반환

2. 접근법

• 문제에서 O(log n)의 시간 복잡도로 문제 해결을 요구했고, nums가 이미 정렬되어 있기 때문에 이진 탐색을 활용하기로 결정
• target이 존재할 때 target의 인덱스를 찾는 것은 별로 어렵지 않게 통과
• 그러나, target이 존재하지 않았을 때 정렬 순서 상 적절하게 삽입되어야 할 인덱스를 어떻게 찾을 지 몰라서 고민
• 여러 테스트 케이스의 패턴을 추적 -> target이 없을 때 left가 적절한 삽입 위치 인덱스인 것을 발견

3. 코드

class Solution {
    public int searchInsert(int[] nums, int target) {
         // 1. 왼쪽, 오른쪽 포인터 선언 및 초기화
         int left = 0; // 첫 인덱스
         int right = nums.length - 1; // 마지막 인덱스

         // 2. 포인터가 교차될 때까지 반복
         while (left <= right) {
            int mid = (left + right) / 2; // 중위 인덱스

            if (nums[mid] < target) {
               left = mid + 1; // 왼쪽 포인터 갱신
            } else if (nums[mid] > target) {
               right = mid - 1; // 오른쪽 포인터 갱신
            } else { // nums[mid] == target
               return mid; // 해당 인덱스 반환
            }
         }

         // 3. target을 찾지 못했을 때 적절한 삽입 인덱스는 left
         return left;
    }
}

4. 성능

- Runtime : 0ms

- Memory : 42.9mb