10.2 이진 탐색으로 삽입 위치 찾기¶

이진 탐색은 목표 원소를 찾는 데만 쓰이는 것이 아니다. 목표 원소를 삽입할 위치를 찾는 등 여러 변형 문제에도 사용할 수 있다.

10.2.1 중복 원소가 없는 경우¶

문제

중복 원소가 없는 길이 \(n\)의 정렬된 배열 nums와 원소 target이 주어진다. 정렬 상태를 유지하면서 target을 배열 nums에 삽입하려고 한다. 이미 target이 있으면 그 왼쪽에 삽입한다. 삽입 후 target의 배열 인덱스를 반환하라. 예시는 아래 그림(10-4)과 같다.

이진 탐색으로 삽입 위치를 찾는 예시 데이터

그림 10-4 이진 탐색으로 삽입 위치를 찾는 예시 데이터

앞 절의 이진 탐색 코드를 재사용하려면 다음 두 질문에 답해야 한다.

질문 1: 배열에 target이 있을 때 삽입 위치의 인덱스는 해당 원소의 인덱스인가?

문제에서는 값이 같은 원소의 왼쪽에 target을 삽입하라고 한다. 따라서 새로 삽입하는 target이 기존 target의 자리를 차지한다. 즉, 배열에 target이 있으면 삽입 위치의 인덱스는 그 target의 인덱스다.

질문 2: 배열에 target이 없을 때 삽입 위치는 어느 원소의 인덱스인가?

이진 탐색 과정을 더 살펴보자. nums[m] < target이면 \(i\)가 이동하므로 포인터 \(i\)는 target 이상인 원소에 가까워진다. 마찬가지로 포인터 \(j\)는 항상 target 이하인 원소에 가까워진다.

따라서 이진 탐색이 끝나면 \(i\)는 target보다 큰 첫 번째 원소를, \(j\)는 target보다 작은 가장 오른쪽 원소를 가리킨다. 배열에 target이 없을 때 삽입 인덱스가 \(i\)임을 쉽게 알 수 있다. 코드는 다음과 같다.

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

binary_search_insertion.py

def binary_search_insertion_simple(nums: list[int], target: int) -> int:
    """삽입 위치의 이진 탐색(중복 원소 없음)"""
    i, j = 0, len(nums) - 1  # 닫힌 구간 [0, n-1]을 초기화한다
    while i <= j:
        m = (i + j) // 2  # 중간 인덱스 m을 계산한다
        if nums[m] < target:
            i = m + 1  # target은 구간 [m+1, j]에 있다
        elif nums[m] > target:
            j = m - 1  # target은 구간 [i, m-1]에 있다
        else:
            return m  # target을 찾았으므로 삽입 위치 m을 반환한다
    # target을 찾지 못했으므로 삽입 위치 i를 반환한다
    return i

binary_search_insertion.cpp

/* 삽입 위치의 이진 탐색(중복 원소 없음) */
int binarySearchInsertionSimple(vector<int> &nums, int target) {
    int i = 0, j = nums.size() - 1; // 닫힌 구간 [0, n-1]을 초기화한다
    while (i <= j) {
        int m = i + (j - i) / 2; // 중간 인덱스 m을 계산한다
        if (nums[m] < target) {
            i = m + 1; // target은 구간 [m+1, j]에 있다
        } else if (nums[m] > target) {
            j = m - 1; // target은 구간 [i, m-1]에 있다
        } else {
            return m; // target을 찾았으므로 삽입 위치 m을 반환한다
        }
    }
    // target을 찾지 못했으므로 삽입 위치 i를 반환한다
    return i;
}

binary_search_insertion.java

/* 삽입 위치의 이진 탐색(중복 원소 없음) */
int binarySearchInsertionSimple(int[] nums, int target) {
    int i = 0, j = nums.length - 1; // 닫힌 구간 [0, n-1]을 초기화한다
    while (i <= j) {
        int m = i + (j - i) / 2; // 중간 인덱스 m을 계산한다
        if (nums[m] < target) {
            i = m + 1; // target은 구간 [m+1, j]에 있다
        } else if (nums[m] > target) {
            j = m - 1; // target은 구간 [i, m-1]에 있다
        } else {
            return m; // target을 찾았으므로 삽입 위치 m을 반환한다
        }
    }
    // target을 찾지 못했으므로 삽입 위치 i를 반환한다
    return i;
}

binary_search_insertion.cs

/* 삽입 위치의 이진 탐색(중복 원소 없음) */
int BinarySearchInsertionSimple(int[] nums, int target) {
    int i = 0, j = nums.Length - 1; // 닫힌 구간 [0, n-1]을 초기화한다
    while (i <= j) {
        int m = i + (j - i) / 2; // 중간 인덱스 m을 계산한다
        if (nums[m] < target) {
            i = m + 1; // target은 구간 [m+1, j]에 있다
        } else if (nums[m] > target) {
            j = m - 1; // target은 구간 [i, m-1]에 있다
        } else {
            return m; // target을 찾았으므로 삽입 위치 m을 반환한다
        }
    }
    // target을 찾지 못했으므로 삽입 위치 i를 반환한다
    return i;
}

binary_search_insertion.go

/* 삽입 위치의 이진 탐색(중복 원소 없음) */
func binarySearchInsertionSimple(nums []int, target int) int {
    // 닫힌 구간 [0, n-1]을 초기화한다
    i, j := 0, len(nums)-1
    for i <= j {
        // 중간 인덱스 m을 계산한다
        m := i + (j-i)/2
        if nums[m] < target {
            // target은 구간 [m+1, j]에 있다
            i = m + 1
        } else if nums[m] > target {
            // target은 구간 [i, m-1]에 있다
            j = m - 1
        } else {
            // target을 찾았으므로 삽입 위치 m을 반환한다
            return m
        }
    }
    // target을 찾지 못했으므로 삽입 위치 i를 반환한다
    return i
}

binary_search_insertion.swift

/* 삽입 위치의 이진 탐색(중복 원소 없음) */
func binarySearchInsertionSimple(nums: [Int], target: Int) -> Int {
    // 닫힌 구간 [0, n-1]을 초기화한다
    var i = nums.startIndex
    var j = nums.endIndex - 1
    while i <= j {
        let m = i + (j - i) / 2 // 중간 인덱스 m을 계산한다
        if nums[m] < target {
            i = m + 1 // target은 구간 [m+1, j]에 있다
        } else if nums[m] > target {
            j = m - 1 // target은 구간 [i, m-1]에 있다
        } else {
            return m // target을 찾았으므로 삽입 위치 m을 반환한다
        }
    }
    // target을 찾지 못했으므로 삽입 위치 i를 반환한다
    return i
}

binary_search_insertion.js

/* 삽입 위치의 이진 탐색(중복 원소 없음) */
function binarySearchInsertionSimple(nums, target) {
    let i = 0,
        j = nums.length - 1; // 닫힌 구간 [0, n-1]을 초기화한다
    while (i <= j) {
        const m = Math.floor(i + (j - i) / 2); // 중간 인덱스 m을 계산하며, Math.floor()로 내림한다
        if (nums[m] < target) {
            i = m + 1; // target은 구간 [m+1, j]에 있다
        } else if (nums[m] > target) {
            j = m - 1; // target은 구간 [i, m-1]에 있다
        } else {
            return m; // target을 찾았으므로 삽입 위치 m을 반환한다
        }
    }
    // target을 찾지 못했으므로 삽입 위치 i를 반환한다
    return i;
}

binary_search_insertion.ts

/* 삽입 위치의 이진 탐색(중복 원소 없음) */
function binarySearchInsertionSimple(
    nums: Array<number>,
    target: number
): number {
    let i = 0,
        j = nums.length - 1; // 닫힌 구간 [0, n-1]을 초기화한다
    while (i <= j) {
        const m = Math.floor(i + (j - i) / 2); // 중간 인덱스 m을 계산하며, Math.floor()로 내림한다
        if (nums[m] < target) {
            i = m + 1; // target은 구간 [m+1, j]에 있다
        } else if (nums[m] > target) {
            j = m - 1; // target은 구간 [i, m-1]에 있다
        } else {
            return m; // target을 찾았으므로 삽입 위치 m을 반환한다
        }
    }
    // target을 찾지 못했으므로 삽입 위치 i를 반환한다
    return i;
}

binary_search_insertion.dart

/* 삽입 위치의 이진 탐색(중복 원소 없음) */
int binarySearchInsertionSimple(List<int> nums, int target) {
  int i = 0, j = nums.length - 1; // 닫힌 구간 [0, n-1]을 초기화한다
  while (i <= j) {
    int m = i + (j - i) ~/ 2; // 중간 인덱스 m을 계산한다
    if (nums[m] < target) {
      i = m + 1; // target은 구간 [m+1, j]에 있다
    } else if (nums[m] > target) {
      j = m - 1; // target은 구간 [i, m-1]에 있다
    } else {
      return m; // target을 찾았으므로 삽입 위치 m을 반환한다
    }
  }
  // target을 찾지 못했으므로 삽입 위치 i를 반환한다
  return i;
}

binary_search_insertion.rs

/* 삽입 위치의 이진 탐색(중복 원소 없음) */
fn binary_search_insertion_simple(nums: &[i32], target: i32) -> i32 {
    let (mut i, mut j) = (0, nums.len() as i32 - 1); // 닫힌 구간 [0, n-1]을 초기화한다
    while i <= j {
        let m = i + (j - i) / 2; // 중간 인덱스 m을 계산한다
        if nums[m as usize] < target {
            i = m + 1; // target은 구간 [m+1, j]에 있다
        } else if nums[m as usize] > target {
            j = m - 1; // target은 구간 [i, m-1]에 있다
        } else {
            return m;
        }
    }
    // target을 찾지 못했으므로 삽입 위치 i를 반환한다
    i
}

binary_search_insertion.c

/* 삽입 위치의 이진 탐색(중복 원소 없음) */
int binarySearchInsertionSimple(int *nums, int numSize, int target) {
    int i = 0, j = numSize - 1; // 닫힌 구간 [0, n-1]을 초기화한다
    while (i <= j) {
        int m = i + (j - i) / 2; // 중간 인덱스 m을 계산한다
        if (nums[m] < target) {
            i = m + 1; // target은 구간 [m+1, j]에 있다
        } else if (nums[m] > target) {
            j = m - 1; // target은 구간 [i, m-1]에 있다
        } else {
            return m; // target을 찾았으므로 삽입 위치 m을 반환한다
        }
    }
    // target을 찾지 못했으므로 삽입 위치 i를 반환한다
    return i;
}

binary_search_insertion.kt

/* 삽입 위치의 이진 탐색(중복 원소 없음) */
fun binarySearchInsertionSimple(nums: IntArray, target: Int): Int {
    var i = 0
    var j = nums.size - 1 // 닫힌 구간 [0, n-1]을 초기화한다
    while (i <= j) {
        val m = i + (j - i) / 2 // 중간 인덱스 m을 계산한다
        if (nums[m] < target) {
            i = m + 1 // target은 구간 [m+1, j]에 있다
        } else if (nums[m] > target) {
            j = m - 1 // target은 구간 [i, m-1]에 있다
        } else {
            return m // target을 찾았으므로 삽입 위치 m을 반환한다
        }
    }
    // target을 찾지 못했으므로 삽입 위치 i를 반환한다
    return i
}

binary_search_insertion.rb

### 삽입 위치의 이진 탐색(중복 원소 없음) ###
def binary_search_insertion_simple(nums, target)
  # 닫힌 구간 [0, n-1]을 초기화한다
  i, j = 0, nums.length - 1

  while i <= j
    # 중간 인덱스 m을 계산한다
    m = (i + j) / 2

    if nums[m] < target
      i = m + 1 # target은 구간 [m+1, j]에 있다
    elsif nums[m] > target
      j = m - 1 # target은 구간 [i, m-1]에 있다
    else
      return m  # target을 찾았으므로 삽입 위치 m을 반환한다
    end
  end

  i # target을 찾지 못했으므로 삽입 위치 i를 반환한다
end

코드 시각화

전체 화면 >

10.2.2 중복 원소가 있는 경우¶

문제

앞 문제에서 배열에 중복 원소가 있을 수 있다는 조건만 추가하고, 나머지 조건은 그대로 둔다.

배열에 target이 여러 개 있다면 일반적인 이진 탐색으로는 그중 하나의 인덱스만 구할 수 있다. 그 원소의 왼쪽과 오른쪽에 target이 몇 개 더 있는지는 알 수 없다.

문제에서는 목표 원소를 가장 왼쪽에 삽입하라고 한다. 따라서 배열에서 가장 왼쪽 target의 인덱스를 찾아야 한다. 먼저 아래 그림(10-5)과 같은 방법을 생각해 볼 수 있다.

이진 탐색으로 임의의 target의 인덱스를 구하고 이를 \(k\)라고 한다.
인덱스 \(k\)부터 왼쪽으로 선형 순회하여 가장 왼쪽 target을 찾으면 반환한다.

선형 탐색으로 중복 원소의 삽입 위치 찾기

그림 10-5 선형 탐색으로 중복 원소의 삽입 위치 찾기

이 방법도 가능하지만 선형 탐색이 포함되어 시간 복잡도가 \(O(n)\)이다. 배열에 중복된 target이 많으면 매우 비효율적이다.

이제 이진 탐색 코드를 확장해 보자. 아래 그림(10-6)과 같이 전체 흐름은 그대로 유지한다. 매 반복에서 중간 인덱스 \(m\)을 계산하고, target과 nums[m]의 대소 관계에 따라 다음과 같이 처리한다.

nums[m] < target 또는 nums[m] > target이면 아직 target을 찾지 못했으므로, 일반적인 이진 탐색처럼 구간을 줄여 포인터 \(i\)와 \(j\)가 target에 가까워지게 한다.
nums[m] == target이면 target보다 작은 원소는 구간 \([i, m - 1]\)에 있으므로, \(j = m - 1\)로 구간을 줄여 포인터 \(j\)가 target보다 작은 원소에 가까워지게 한다.

반복이 끝나면 \(i\)는 가장 왼쪽 target을, \(j\)는 target보다 작은 가장 오른쪽 원소를 가리킨다. 따라서 인덱스 \(i\)가 삽입 위치다.

그림 10-6 이진 탐색으로 중복 원소의 삽입 위치를 찾는 단계

아래 코드를 보면 nums[m] > target과 nums[m] == target 분기에서 수행하는 연산이 같으므로 두 분기를 합칠 수 있다.

그렇더라도 조건을 나누어 두면 논리가 더 명확하고 가독성이 좋으므로 그대로 둘 수 있다.