[리트코드] 35 - Search Insert Position

35. Search Insert Position

Easy

---

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

 

Example 1:

Input: nums = [1,3,5,6], target = 5
Output: 2

Example 2:

Input: nums = [1,3,5,6], target = 2
Output: 1

Example 3:

Input: nums = [1,3,5,6], target = 7
Output: 4

 

Constraints:

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums contains distinct values sorted in ascending order.
• -104 <= target <= 104

분류

배열, 이분 탐색

---

문제 풀이

문제 분석

이 문제는 오름차순으로 정렬된 중복 없는 정수 배열과 타겟 값이 주어졌을 때, 타겟이 배열에 존재하면 그 인덱스를 반환하고, 존재하지 않으면 타겟이 정렬 순서를 유지하며 삽입되어야 할 위치의 인덱스를 반환하는 것입니다.

• 입력: 정렬된 정수 리스트 nums, 정수 target
• 출력: 정수 (인덱스)
• 제약 조건: 시간 복잡도 O(log n)을 만족해야 하므로 선형 탐색(O(n))을 사용할 수 없고, 이분 탐색(Binary Search)을 사용해야 합니다.

접근 방법

이 문제는 정렬된 배열에서 특정 값을 찾거나, 값이 없을 때 삽입 위치를 찾아야 하므로 이분 탐색(Binary Search) 알고리즘이 가장 적합합니다.

이분 탐색을 선택한 이유:

1. 배열이 이미 정렬되어 있습니다.
2. 시간 복잡도 O(log n)이 요구됩니다.
3. 탐색 범위를 절반으로 좁혀가며 타겟의 위치를 특정할 수 있습니다.

탐색 종료 조건은 left > right가 되는 시점입니다. 이 시점에 left 포인터는 타겟이 삽입되어야 할 정확한 위치를 가리키게 됩니다. (타겟보다 작은 값들의 바로 오른쪽, 타겟보다 큰 값들의 바로 왼쪽)

구현 설명

1. 초기화 및 탐색 범위 설정

n = len(nums)
left = 0
right = n - 1

• 배열의 길이 n을 구하고, 탐색 범위의 시작(left)을 0, 끝(right)을 n-1로 초기화합니다.

2. 이분 탐색 루프 실행

while left <= right:
    mid = (left + right) // 2
    ...

• left가 right보다 작거나 같은 동안 루프를 돌며 중간 인덱스 mid를 계산합니다.
• left <= right 조건을 사용하여 타겟이 배열의 맨 앞이나 맨 뒤에 삽입되는 경우까지 모두 커버합니다.

3. 중간 값 비교 및 범위 좁히기

if nums[mid] == target:
    return mid
elif nums[mid] < target:
    left = mid + 1
else:
    right = mid - 1

• 타겟 발견 시: nums[mid] == target이면 즉시 mid 인덱스를 반환합니다.
• 타겟이 중간 값보다 큰 경우: 타겟은 중간 인덱스의 오른쪽 구간에 있으므로 left = mid + 1로 시작점을 옮깁니다.
• 타겟이 중간 값보다 작은 경우: 타겟은 중간 인덱스의 왼쪽 구간에 있으므로 right = mid - 1로 끝점을 옮깁니다.

4. 삽입 위치 반환

return left

• 루프가 종료되었다는 것은 left > right 상태가 되었다는 뜻이며, 배열 내에 타겟이 없음을 의미합니다.
• 이 시점 left는 타겟보다 큰 첫 번째 원소의 인덱스이거나, 모든 원소보다 타겟이 커서 배열 길이 n과 같은 값이 됩니다. 즉, 정렬 순서를 유지하며 타겟이 들어가야 할 정확한 위치입니다.

⏱복잡도 분석

• 시간 복잡도: O(log n)
  • 이분 탐색을 사용하므로 매 반복마다 탐색 범위가 절반으로 줄어듭니다. 배열의 크기 n에 대해 최대 log₂n번 연산이 수행됩니다.
• 공간 복잡도: O(1)
  • 몇 개의 정수 변수(left, right, mid, n)만 사용하므로 입력 크기와 무관하게 상수 공간만 사용합니다.

핵심 포인트

1. **이분 탐색의 종료 조건(left <= right)**을 사용하여 타겟이 없을 때의 삽입 위치까지 자연스럽게 처리합니다.
2. 탐색 실패 시 left 포인터의 의미를 이해해야 합니다. left는 "타겟보다 큰 최초의 원소 인덱스"이자 "삽입 위치"가 됩니다.
3. 오버플로우 방지를 위해 Python에서는 (left + right) // 2로 충분하지만, 다른 언어(Java, C++ 등)에서는 left + (right - left) // 2 방식을 쓰는 것이 안전합니다.

풀이 코드

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        n = len(nums)
        left = 0
        right = n - 1
        while left <= right:
            mid = (left+right)//2

            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        return left