10.3 이진 탐색으로 경계 찾기¶

10.3.1 왼쪽 경계 찾기¶

문제

중복 원소를 포함할 수 있는 길이 \(n\)의 정렬된 배열 nums가 주어진다. 배열에서 가장 왼쪽에 있는 원소 target의 인덱스를 반환하라. 해당 원소가 없으면 \(-1\)을 반환하라.

이진 탐색으로 삽입 위치를 찾는 방법을 떠올려 보자. 탐색이 끝나면 \(i\)는 가장 왼쪽의 target을 가리킨다. 따라서 삽입 위치 찾기는 본질적으로 가장 왼쪽 target의 인덱스를 찾는 과정이다.

삽입 위치를 찾는 함수를 이용하여 왼쪽 경계를 찾아 보자. 배열에 target이 없을 수도 있으며, 이때는 다음 두 결과 중 하나가 나올 수 있다.

삽입 위치의 인덱스 \(i\)가 범위를 벗어난다.
원소 nums[i]가 target과 다르다.

위 두 경우에는 \(-1\)을 바로 반환하면 된다. 코드는 다음과 같다.

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

binary_search_edge.py

def binary_search_left_edge(nums: list[int], target: int) -> int:
    """가장 왼쪽에 있는 target을 이진 탐색"""
    # target의 삽입 위치를 찾는 것과 같다
    i = binary_search_insertion(nums, target)
    # target을 찾지 못했으므로 -1을 반환한다
    if i == len(nums) or nums[i] != target:
        return -1
    # target을 찾았으므로 인덱스 i를 반환한다
    return i

binary_search_edge.cpp

/* 가장 왼쪽에 있는 target을 이진 탐색 */
int binarySearchLeftEdge(vector<int> &nums, int target) {
    // target의 삽입 위치를 찾는 것과 같다
    int i = binarySearchInsertion(nums, target);
    // target을 찾지 못했으므로 -1을 반환한다
    if (i == nums.size() || nums[i] != target) {
        return -1;
    }
    // target을 찾았으므로 인덱스 i를 반환한다
    return i;
}

binary_search_edge.java

/* 가장 왼쪽에 있는 target을 이진 탐색 */
int binarySearchLeftEdge(int[] nums, int target) {
    // target의 삽입 위치를 찾는 것과 같다
    int i = binary_search_insertion.binarySearchInsertion(nums, target);
    // target을 찾지 못했으므로 -1을 반환한다
    if (i == nums.length || nums[i] != target) {
        return -1;
    }
    // target을 찾았으므로 인덱스 i를 반환한다
    return i;
}

binary_search_edge.cs

/* 가장 왼쪽에 있는 target을 이진 탐색 */
int BinarySearchLeftEdge(int[] nums, int target) {
    // target의 삽입 위치를 찾는 것과 같다
    int i = binary_search_insertion.BinarySearchInsertion(nums, target);
    // target을 찾지 못했으므로 -1을 반환한다
    if (i == nums.Length || nums[i] != target) {
        return -1;
    }
    // target을 찾았으므로 인덱스 i를 반환한다
    return i;
}

binary_search_edge.go

/* 가장 왼쪽에 있는 target을 이진 탐색 */
func binarySearchLeftEdge(nums []int, target int) int {
    // target의 삽입 위치를 찾는 것과 같다
    i := binarySearchInsertion(nums, target)
    // target을 찾지 못했으므로 -1을 반환한다
    if i == len(nums) || nums[i] != target {
        return -1
    }
    // target을 찾았으므로 인덱스 i를 반환한다
    return i
}

binary_search_edge.swift

/* 가장 왼쪽에 있는 target을 이진 탐색 */
func binarySearchLeftEdge(nums: [Int], target: Int) -> Int {
    // target의 삽입 위치를 찾는 것과 같다
    let i = binarySearchInsertion(nums: nums, target: target)
    // target을 찾지 못했으므로 -1을 반환한다
    if i == nums.endIndex || nums[i] != target {
        return -1
    }
    // target을 찾았으므로 인덱스 i를 반환한다
    return i
}

binary_search_edge.js

/* 가장 왼쪽에 있는 target을 이진 탐색 */
function binarySearchLeftEdge(nums, target) {
    // target의 삽입 위치를 찾는 것과 같다
    const i = binarySearchInsertion(nums, target);
    // target을 찾지 못했으므로 -1을 반환한다
    if (i === nums.length || nums[i] !== target) {
        return -1;
    }
    // target을 찾았으므로 인덱스 i를 반환한다
    return i;
}

binary_search_edge.ts

/* 가장 왼쪽에 있는 target을 이진 탐색 */
function binarySearchLeftEdge(nums: Array<number>, target: number): number {
    // target의 삽입 위치를 찾는 것과 같다
    const i = binarySearchInsertion(nums, target);
    // target을 찾지 못했으므로 -1을 반환한다
    if (i === nums.length || nums[i] !== target) {
        return -1;
    }
    // target을 찾았으므로 인덱스 i를 반환한다
    return i;
}

binary_search_edge.dart

/* 가장 왼쪽에 있는 target을 이진 탐색 */
int binarySearchLeftEdge(List<int> nums, int target) {
  // target의 삽입 위치를 찾는 것과 같다
  int i = binarySearchInsertion(nums, target);
  // target을 찾지 못했으므로 -1을 반환한다
  if (i == nums.length || nums[i] != target) {
    return -1;
  }
  // target을 찾았으므로 인덱스 i를 반환한다
  return i;
}

binary_search_edge.rs

/* 가장 왼쪽에 있는 target을 이진 탐색 */
fn binary_search_left_edge(nums: &[i32], target: i32) -> i32 {
    // target의 삽입 위치를 찾는 것과 같다
    let i = binary_search_insertion(nums, target);
    // target을 찾지 못했으므로 -1을 반환한다
    if i == nums.len() as i32 || nums[i as usize] != target {
        return -1;
    }
    // target을 찾았으므로 인덱스 i를 반환한다
    i
}

binary_search_edge.c

/* 가장 왼쪽에 있는 target을 이진 탐색 */
int binarySearchLeftEdge(int *nums, int numSize, int target) {
    // target의 삽입 위치를 찾는 것과 같다
    int i = binarySearchInsertion(nums, numSize, target);
    // target을 찾지 못했으므로 -1을 반환한다
    if (i == numSize || nums[i] != target) {
        return -1;
    }
    // target을 찾았으므로 인덱스 i를 반환한다
    return i;
}

binary_search_edge.kt

/* 가장 왼쪽에 있는 target을 이진 탐색 */
fun binarySearchLeftEdge(nums: IntArray, target: Int): Int {
    // target의 삽입 위치를 찾는 것과 같다
    val i = binarySearchInsertion(nums, target)
    // target을 찾지 못했으므로 -1을 반환한다
    if (i == nums.size || nums[i] != target) {
        return -1
    }
    // target을 찾았으므로 인덱스 i를 반환한다
    return i
}

binary_search_edge.rb

### 가장 왼쪽에 있는 target을 이진 탐색 ###
def binary_search_left_edge(nums, target)
  # target의 삽입 위치를 찾는 것과 같다
  i = binary_search_insertion(nums, target)

  # target을 찾지 못했으므로 -1을 반환한다
  return -1 if i == nums.length || nums[i] != target

  i # target을 찾았으므로 인덱스 i를 반환한다
end

코드 시각화

전체 화면 >

10.3.2 오른쪽 경계 찾기¶

가장 오른쪽에 있는 target은 어떻게 찾을까? 가장 직접적인 방법은 코드를 수정하여 nums[m] == target일 때 포인터로 구간을 줄이는 방식을 바꾸는 것이다. 코드는 생략하니, 관심 있는 독자는 직접 구현해 보자.

아래에서는 더 기발한 두 가지 방법을 소개한다.

1. 왼쪽 경계 찾기 재활용¶

가장 왼쪽 원소를 찾는 함수로 가장 오른쪽 원소도 찾을 수 있다. 구체적으로는 가장 오른쪽 target을 찾는 문제를 가장 왼쪽 target + 1을 찾는 문제로 바꾼다.

아래 그림(10-7)과 같이 탐색이 끝나면 포인터 \(i\)는 가장 왼쪽 target + 1(존재한다면)을 가리키고, \(j\)는 가장 오른쪽 target을 가리킨다. 따라서 \(j\)를 반환하면 된다.

오른쪽 경계 찾기를 왼쪽 경계 찾기로 변환

그림 10-7 오른쪽 경계 찾기를 왼쪽 경계 찾기로 변환

반환되는 삽입 위치는 \(i\)이므로, 여기서 \(1\)을 빼야 \(j\)를 얻을 수 있다.