[Algorithm][LeetCode 35] Search Insert Position

이진 탐색을 활용한 삽입 위치 찾기 (O(log n))

정렬된 배열이 주어졌을 때, 특정 target 값을 찾고, 해당 값이 존재하지 않는다면 정렬된 상태를 유지하면서 삽입할 수 있는 위치를 반환하는 문제입니다.

<문제>

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.

<예제>

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

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

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

<제약사항>

• 1 <= nums.length <= 10⁴
• -10⁴ <= nums[i], target <= 10⁴
• nums는 오름차순 정렬된 상태이며, 모든 값은 중복되지 않습니다.

<솔루션>

기본적인 이진 탐색 패턴을 적용하면 문제를 효율적으로 해결할 수 있습니다.

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    let left = 0;
    let right = nums.length - 1;
    let mid;
    
    while (left <= right) {
        mid = Math.floor((left + right) / 2);
        if (nums[mid] === target) return mid;
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return left;
};

<참고>

1. 이진 탐색에서 left, right의 의미

• left: target이 있을 수 있는 범위의 시작
• right: target이 있을 수 있는 범위의 끝
• 이진 탐색 종료 시점에 left > right가 되며, 다음이 성립합니다.
  • left: target이 삽입되어야 할 정확한 위치
  • right: 그 이전 위치

이진 탐색의 탐색 범위가 좁아지면서 target보다 작은 요소들을 제외하게 되고, 결국 남는 위치는 target이 들어가야 할 위치인 left가 됩니다. 이는 다음의 범위 조건으로 설명할 수 있습니다.

nums[0..left-1] < target <= nums[left..]

즉, target보다 작은 값들은 모두 left 이전에 있고, target 이상인 값들은 left 이후에 존재하게 되는 구조입니다.

2. Lower Bound 패턴

위 로직은 Lower Bound 이진 탐색 패턴에 해당합니다. 이 패턴은 다음과 같은 경우에 활용됩니다.

• 삽입 위치 찾기 (Insert Position)
• 특정 값이 처음 등장하는 위치 찾기 (First Occurrence)
• 특정 조건을 처음 만족하는 값 찾기

3. Upper Bound 패턴

Upper Bound는 target보다 큰 값이 처음 나오는 위치를 찾는 패턴입니다.

예시: nums = [1, 3, 5, 6], target = 5

Lower Bound: target 이상인 첫 위치 → index 2

Upper Bound: target 초과인 첫 위치 → index 3 (값은 6)

function upperBound(nums, target) {
    let left = 0;
    let right = nums.length;

    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return left;
}

동작 흐름

nums = [1, 3, 5, 6], target = 5
초기 left = 0, right = 4

1. mid = 2, nums[2] = 5 → 5 <= 5 → left = 3
2. mid = 3, nums[3] = 6 → 6 > 5 → right = 3

종료: left = 3 → upper bound 위치

마무리

이진 탐색은 단순히 값을 찾는 데 그치지 않고, 조건에 맞는 위치를 정확히 찾아주는 강력한 도구입니다. 특히 삽입 위치나 경계 조건을 다룰 때, lower bound / upper bound 개념을 정확히 이해하고 사용하면 문제 해결이 매우 수월해집니다.