10.1 이진 탐색¶

이진 탐색(binary search)은 분할 정복 전략에 기반한 효율적인 탐색 알고리즘이다. 데이터가 정렬되어 있다는 성질을 이용하여 매번 탐색 범위를 절반으로 줄이며, 목표 원소를 찾거나 탐색 구간이 빌 때까지 반복한다.

문제

길이가 \(n\)인 배열 nums가 주어진다. 원소는 오름차순으로 정렬되어 있고 중복되지 않는다. 이 배열에서 원소 target을 찾아 그 인덱스를 반환하라. 배열에 해당 원소가 없으면 \(-1\)을 반환하라. 예시는 아래 그림(10-1)과 같다.

이진 탐색 예시 데이터

그림 10-1 이진 탐색 예시 데이터

아래 그림(10-2)과 같이 포인터 \(i = 0\)과 \(j = n - 1\)을 초기화하여 각각 배열의 첫 원소와 마지막 원소를 가리키게 한다. 이는 탐색 구간 \([0, n - 1]\)을 나타낸다. 대괄호는 경곗값 자체를 포함하는 닫힌 구간을 뜻한다.

이어서 다음 두 단계를 반복한다.

중간 인덱스 \(m = \lfloor {(i + j) / 2} \rfloor\)를 계산한다. 여기서 \(\lfloor \: \rfloor\)는 내림 연산이다.
nums[m]과 target의 대소 관계를 비교하며, 다음 세 경우로 나뉜다.
1. nums[m] < target이면 target은 구간 \([m + 1, j]\)에 있으므로 \(i = m + 1\)을 수행한다.
2. nums[m] > target이면 target은 구간 \([i, m - 1]\)에 있으므로 \(j = m - 1\)을 수행한다.
3. nums[m] = target이면 target을 찾았으므로 인덱스 \(m\)을 반환한다.

배열에 목표 원소가 없으면 탐색 구간은 결국 비게 된다. 이때 \(-1\)을 반환한다.

그림 10-2 이진 탐색 과정

\(i\)와 \(j\)가 모두 int 타입이므로 \(i + j\)가 int 타입의 표현 범위를 벗어날 수 있다. 정수 오버플로를 피하기 위해 보통 \(m = \lfloor {i + (j - i) / 2} \rfloor\) 공식으로 중간 인덱스를 계산한다.

코드는 다음과 같다.

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

binary_search.py

def binary_search(nums: list[int], target: int) -> int:
    """이진 탐색(양 끝을 포함하는 닫힌 구간)"""
    # 닫힌 구간 [0, n-1]을 초기화한다. i와 j는 각각 배열의 첫 원소와 마지막 원소를 가리킨다
    i, j = 0, len(nums) - 1
    # 반복하다 탐색 구간이 비면 종료한다(i > j이면 빈 구간이다)
    while i <= j:
        # 이론적으로 Python의 수는 메모리 크기에 따라 무한히 커질 수 있으므로 큰 수의 범위 초과를 고려할 필요가 없다
        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  # 목표 원소를 찾았으므로 해당 인덱스를 반환한다
    return -1  # 목표 원소를 찾지 못했으므로 -1을 반환한다

binary_search.cpp

/* 이진 탐색(양 끝을 포함하는 닫힌 구간) */
int binarySearch(vector<int> &nums, int target) {
    // 닫힌 구간 [0, n-1]을 초기화한다. i와 j는 각각 배열의 첫 원소와 마지막 원소를 가리킨다
    int i = 0, j = nums.size() - 1;
    // 반복하다 탐색 구간이 비면 종료한다(i > j이면 빈 구간이다)
    while (i <= j) {
        int m = i + (j - i) / 2; // 중간 인덱스 m을 계산한다
        if (nums[m] < target)    // 이 경우 target은 구간 [m+1, j]에 있다
            i = m + 1;
        else if (nums[m] > target) // 이 경우 target은 구간 [i, m-1]에 있다
            j = m - 1;
        else // 목표 원소를 찾았으므로 해당 인덱스를 반환한다
            return m;
    }
    // 목표 원소를 찾지 못했으므로 -1을 반환한다
    return -1;
}

binary_search.java

/* 이진 탐색(양 끝을 포함하는 닫힌 구간) */
int binarySearch(int[] nums, int target) {
    // 닫힌 구간 [0, n-1]을 초기화한다. i와 j는 각각 배열의 첫 원소와 마지막 원소를 가리킨다
    int i = 0, j = nums.length - 1;
    // 반복하다 탐색 구간이 비면 종료한다(i > j이면 빈 구간이다)
    while (i <= j) {
        int m = i + (j - i) / 2; // 중간 인덱스 m을 계산한다
        if (nums[m] < target) // 이 경우 target은 구간 [m+1, j]에 있다
            i = m + 1;
        else if (nums[m] > target) // 이 경우 target은 구간 [i, m-1]에 있다
            j = m - 1;
        else // 목표 원소를 찾았으므로 해당 인덱스를 반환한다
            return m;
    }
    // 목표 원소를 찾지 못했으므로 -1을 반환한다
    return -1;
}

binary_search.cs

/* 이진 탐색(양 끝을 포함하는 닫힌 구간) */
int BinarySearch(int[] nums, int target) {
    // 닫힌 구간 [0, n-1]을 초기화한다. i와 j는 각각 배열의 첫 원소와 마지막 원소를 가리킨다
    int i = 0, j = nums.Length - 1;
    // 반복하다 탐색 구간이 비면 종료한다(i > j이면 빈 구간이다)
    while (i <= j) {
        int m = i + (j - i) / 2;   // 중간 인덱스 m을 계산한다
        if (nums[m] < target)      // 이 경우 target은 구간 [m+1, j]에 있다
            i = m + 1;
        else if (nums[m] > target) // 이 경우 target은 구간 [i, m-1]에 있다
            j = m - 1;
        else                       // 목표 원소를 찾았으므로 해당 인덱스를 반환한다
            return m;
    }
    // 목표 원소를 찾지 못했으므로 -1을 반환한다
    return -1;
}

binary_search.go

/* 이진 탐색(양 끝을 포함하는 닫힌 구간) */
func binarySearch(nums []int, target int) int {
    // 닫힌 구간 [0, n-1]을 초기화한다. i와 j는 각각 배열의 첫 원소와 마지막 원소를 가리킨다
    i, j := 0, len(nums)-1
    // 반복하다 탐색 구간이 비면 종료한다(i > j이면 빈 구간이다)
    for i <= j {
        m := i + (j-i)/2      // 중간 인덱스 m을 계산한다
        if nums[m] < target { // 이 경우 target은 구간 [m+1, j]에 있다
            i = m + 1
        } else if nums[m] > target { // 이 경우 target은 구간 [i, m-1]에 있다
            j = m - 1
        } else { // 목표 원소를 찾았으므로 해당 인덱스를 반환한다
            return m
        }
    }
    // 목표 원소를 찾지 못했으므로 -1을 반환한다
    return -1
}

binary_search.swift

/* 이진 탐색(양 끝을 포함하는 닫힌 구간) */
func binarySearch(nums: [Int], target: Int) -> Int {
    // 닫힌 구간 [0, n-1]을 초기화한다. i와 j는 각각 배열의 첫 원소와 마지막 원소를 가리킨다
    var i = nums.startIndex
    var j = nums.endIndex - 1
    // 반복하다 탐색 구간이 비면 종료한다(i > j이면 빈 구간이다)
    while i <= j {
        let m = i + (j - i) / 2 // 중간 인덱스 m을 계산한다
        if nums[m] < target { // 이 경우 target은 구간 [m+1, j]에 있다
            i = m + 1
        } else if nums[m] > target { // 이 경우 target은 구간 [i, m-1]에 있다
            j = m - 1
        } else { // 목표 원소를 찾았으므로 해당 인덱스를 반환한다
            return m
        }
    }
    // 목표 원소를 찾지 못했으므로 -1을 반환한다
    return -1
}

binary_search.js

/* 이진 탐색(양 끝을 포함하는 닫힌 구간) */
function binarySearch(nums, target) {
    // 닫힌 구간 [0, n-1]을 초기화한다. i와 j는 각각 배열의 첫 원소와 마지막 원소를 가리킨다
    let i = 0,
        j = nums.length - 1;
    // 반복하다 탐색 구간이 비면 종료한다(i > j이면 빈 구간이다)
    while (i <= j) {
        // 중간 인덱스 m을 계산하며, parseInt()로 소수 부분을 버린다
        const m = parseInt(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 return m; // 목표 원소를 찾았으므로 해당 인덱스를 반환한다
    }
    // 목표 원소를 찾지 못했으므로 -1을 반환한다
    return -1;
}

binary_search.ts

/* 이진 탐색(양 끝을 포함하는 닫힌 구간) */
function binarySearch(nums: number[], target: number): number {
    // 닫힌 구간 [0, n-1]을 초기화한다. i와 j는 각각 배열의 첫 원소와 마지막 원소를 가리킨다
    let i = 0,
        j = nums.length - 1;
    // 반복하다 탐색 구간이 비면 종료한다(i > j이면 빈 구간이다)
    while (i <= j) {
        // 중간 인덱스 m을 계산한다
        const m = Math.floor(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 {
            // 목표 원소를 찾았으므로 해당 인덱스를 반환한다
            return m;
        }
    }
    return -1; // 목표 원소를 찾지 못했으므로 -1을 반환한다
}

binary_search.dart

/* 이진 탐색(양 끝을 포함하는 닫힌 구간) */
int binarySearch(List<int> nums, int target) {
  // 닫힌 구간 [0, n-1]을 초기화한다. i와 j는 각각 배열의 첫 원소와 마지막 원소를 가리킨다
  int i = 0, j = nums.length - 1;
  // 반복하다 탐색 구간이 비면 종료한다(i > j이면 빈 구간이다)
  while (i <= j) {
    int m = i + (j - i) ~/ 2; // 중간 인덱스 m을 계산한다
    if (nums[m] < target) {
      // 이 경우 target은 구간 [m+1, j]에 있다
      i = m + 1;
    } else if (nums[m] > target) {
      // 이 경우 target은 구간 [i, m-1]에 있다
      j = m - 1;
    } else {
      // 목표 원소를 찾았으므로 해당 인덱스를 반환한다
      return m;
    }
  }
  // 목표 원소를 찾지 못했으므로 -1을 반환한다
  return -1;
}

binary_search.rs

/* 이진 탐색(양 끝을 포함하는 닫힌 구간) */
fn binary_search(nums: &[i32], target: i32) -> i32 {
    // 닫힌 구간 [0, n-1]을 초기화한다. i와 j는 각각 배열의 첫 원소와 마지막 원소를 가리킨다
    let mut i = 0;
    let mut j = nums.len() as i32 - 1;
    // 반복하다 탐색 구간이 비면 종료한다(i > j이면 빈 구간이다)
    while i <= j {
        let m = i + (j - i) / 2; // 중간 인덱스 m을 계산한다
        if nums[m as usize] < target {
            // 이 경우 target은 구간 [m+1, j]에 있다
            i = m + 1;
        } else if nums[m as usize] > target {
            // 이 경우 target은 구간 [i, m-1]에 있다
            j = m - 1;
        } else {
            // 목표 원소를 찾았으므로 해당 인덱스를 반환한다
            return m;
        }
    }
    // 목표 원소를 찾지 못했으므로 -1을 반환한다
    return -1;
}

binary_search.c

/* 이진 탐색(양 끝을 포함하는 닫힌 구간) */
int binarySearch(int *nums, int len, int target) {
    // 닫힌 구간 [0, n-1]을 초기화한다. i와 j는 각각 배열의 첫 원소와 마지막 원소를 가리킨다
    int i = 0, j = len - 1;
    // 반복하다 탐색 구간이 비면 종료한다(i > j이면 빈 구간이다)
    while (i <= j) {
        int m = i + (j - i) / 2; // 중간 인덱스 m을 계산한다
        if (nums[m] < target)    // 이 경우 target은 구간 [m+1, j]에 있다
            i = m + 1;
        else if (nums[m] > target) // 이 경우 target은 구간 [i, m-1]에 있다
            j = m - 1;
        else // 목표 원소를 찾았으므로 해당 인덱스를 반환한다
            return m;
    }
    // 목표 원소를 찾지 못했으므로 -1을 반환한다
    return -1;
}

binary_search.kt

/* 이진 탐색(양 끝을 포함하는 닫힌 구간) */
fun binarySearch(nums: IntArray, target: Int): Int {
    // 닫힌 구간 [0, n-1]을 초기화한다. i와 j는 각각 배열의 첫 원소와 마지막 원소를 가리킨다
    var i = 0
    var j = nums.size - 1
    // 반복하다 탐색 구간이 비면 종료한다(i > j이면 빈 구간이다)
    while (i <= j) {
        val m = i + (j - i) / 2 // 중간 인덱스 m을 계산한다
        if (nums[m] < target) // 이 경우 target은 구간 [m+1, j]에 있다
            i = m + 1
        else if (nums[m] > target) // 이 경우 target은 구간 [i, m-1]에 있다
            j = m - 1
        else  // 목표 원소를 찾았으므로 해당 인덱스를 반환한다
            return m
    }
    // 목표 원소를 찾지 못했으므로 -1을 반환한다
    return -1
}

binary_search.rb

### 이진 탐색(양 끝을 포함하는 닫힌 구간) ###
def binary_search(nums, target)
  # 닫힌 구간 [0, n-1]을 초기화한다. i와 j는 각각 배열의 첫 원소와 마지막 원소를 가리킨다
  i, j = 0, nums.length - 1

  # 반복하다 탐색 구간이 비면 종료한다(i > j이면 빈 구간이다)
  while i <= j
    # Ruby의 정수는 이론상 메모리가 허용하는 만큼 커질 수 있으므로 큰 수의 오버플로를 고려할 필요가 없다
    m = (i + j) / 2   # 중간 인덱스 m을 계산한다

    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  # 목표 원소를 찾았으므로 해당 인덱스를 반환한다
    end
  end

  -1  # 목표 원소를 찾지 못했으므로 -1을 반환한다
end

코드 시각화

전체 화면 >

시간 복잡도는 \(O(\log n)\)이다. 이진 탐색의 반복문에서 구간이 매번 절반으로 줄어들므로 반복 횟수는 \(\log_2 n\)이다.

공간 복잡도는 \(O(1)\)이다. 포인터 \(i\)와 \(j\)는 상수 크기의 공간을 사용한다.

10.1.1 구간 표현 방법¶

위의 양끝이 닫힌 구간 외에 '왼쪽은 닫히고 오른쪽은 열린' 구간도 자주 사용한다. \([0, n)\)으로 정의하며 왼쪽 경곗값은 포함하고 오른쪽 경곗값은 포함하지 않는다. 이 표현에서 구간 \([i, j)\)는 \(i = j\)일 때 비어 있다.

이 표현을 사용하여 같은 기능의 이진 탐색 알고리즘을 구현할 수 있다.

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

binary_search.py

def binary_search_lcro(nums: list[int], target: int) -> int:
    """이진 탐색(왼쪽 끝은 포함하고 오른쪽 끝은 제외하는 구간)"""
    # 왼쪽 끝만 포함하는 구간 [0, n)을 초기화한다. i는 배열의 첫 원소를, j는 마지막 원소 바로 다음 위치를 가리킨다
    i, j = 0, len(nums)
    # 반복하다 탐색 구간이 비면 종료한다(i = j이면 빈 구간이다)
    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  # 이 경우 target은 구간 [i, m)에 있다
        else:
            return m  # 목표 원소를 찾았으므로 해당 인덱스를 반환한다
    return -1  # 목표 원소를 찾지 못했으므로 -1을 반환한다

binary_search.cpp

/* 이진 탐색(왼쪽 끝은 포함하고 오른쪽 끝은 제외하는 구간) */
int binarySearchLCRO(vector<int> &nums, int target) {
    // 왼쪽 끝만 포함하는 구간 [0, n)을 초기화한다. i는 배열의 첫 원소를, j는 마지막 원소 바로 다음 위치를 가리킨다
    int i = 0, j = nums.size();
    // 반복하다 탐색 구간이 비면 종료한다(i = j이면 빈 구간이다)
    while (i < j) {
        int m = i + (j - i) / 2; // 중간 인덱스 m을 계산한다
        if (nums[m] < target)    // 이 경우 target은 구간 [m+1, j)에 있다
            i = m + 1;
        else if (nums[m] > target) // 이 경우 target은 구간 [i, m)에 있다
            j = m;
        else // 목표 원소를 찾았으므로 해당 인덱스를 반환한다
            return m;
    }
    // 목표 원소를 찾지 못했으므로 -1을 반환한다
    return -1;
}

binary_search.java

/* 이진 탐색(왼쪽 끝은 포함하고 오른쪽 끝은 제외하는 구간) */
int binarySearchLCRO(int[] nums, int target) {
    // 왼쪽 끝만 포함하는 구간 [0, n)을 초기화한다. i는 배열의 첫 원소를, j는 마지막 원소 바로 다음 위치를 가리킨다
    int i = 0, j = nums.length;
    // 반복하다 탐색 구간이 비면 종료한다(i = j이면 빈 구간이다)
    while (i < j) {
        int m = i + (j - i) / 2; // 중간 인덱스 m을 계산한다
        if (nums[m] < target) // 이 경우 target은 구간 [m+1, j)에 있다
            i = m + 1;
        else if (nums[m] > target) // 이 경우 target은 구간 [i, m)에 있다
            j = m;
        else // 목표 원소를 찾았으므로 해당 인덱스를 반환한다
            return m;
    }
    // 목표 원소를 찾지 못했으므로 -1을 반환한다
    return -1;
}

binary_search.cs

/* 이진 탐색(왼쪽 끝은 포함하고 오른쪽 끝은 제외하는 구간) */
int BinarySearchLCRO(int[] nums, int target) {
    // 왼쪽 끝만 포함하는 구간 [0, n)을 초기화한다. i는 배열의 첫 원소를, j는 마지막 원소 바로 다음 위치를 가리킨다
    int i = 0, j = nums.Length;
    // 반복하다 탐색 구간이 비면 종료한다(i = j이면 빈 구간이다)
    while (i < j) {
        int m = i + (j - i) / 2;   // 중간 인덱스 m을 계산한다
        if (nums[m] < target)      // 이 경우 target은 구간 [m+1, j)에 있다
            i = m + 1;
        else if (nums[m] > target) // 이 경우 target은 구간 [i, m)에 있다
            j = m;
        else                       // 목표 원소를 찾았으므로 해당 인덱스를 반환한다
            return m;
    }
    // 목표 원소를 찾지 못했으므로 -1을 반환한다
    return -1;
}

binary_search.go

/* 이진 탐색(왼쪽 끝은 포함하고 오른쪽 끝은 제외하는 구간) */
func binarySearchLCRO(nums []int, target int) int {
    // 왼쪽 끝만 포함하는 구간 [0, n)을 초기화한다. i는 배열의 첫 원소를, j는 마지막 원소 바로 다음 위치를 가리킨다
    i, j := 0, len(nums)
    // 반복하다 탐색 구간이 비면 종료한다(i = j이면 빈 구간이다)
    for i < j {
        m := i + (j-i)/2      // 중간 인덱스 m을 계산한다
        if nums[m] < target { // 이 경우 target은 구간 [m+1, j)에 있다
            i = m + 1
        } else if nums[m] > target { // 이 경우 target은 구간 [i, m)에 있다
            j = m
        } else { // 목표 원소를 찾았으므로 해당 인덱스를 반환한다
            return m
        }
    }
    // 목표 원소를 찾지 못했으므로 -1을 반환한다
    return -1
}

binary_search.swift

/* 이진 탐색(왼쪽 끝은 포함하고 오른쪽 끝은 제외하는 구간) */
func binarySearchLCRO(nums: [Int], target: Int) -> Int {
    // 왼쪽 끝만 포함하는 구간 [0, n)을 초기화한다. i는 배열의 첫 원소를, j는 마지막 원소 바로 다음 위치를 가리킨다
    var i = nums.startIndex
    var j = nums.endIndex
    // 반복하다 탐색 구간이 비면 종료한다(i = j이면 빈 구간이다)
    while i < j {
        let m = i + (j - i) / 2 // 중간 인덱스 m을 계산한다
        if nums[m] < target { // 이 경우 target은 구간 [m+1, j)에 있다
            i = m + 1
        } else if nums[m] > target { // 이 경우 target은 구간 [i, m)에 있다
            j = m
        } else { // 목표 원소를 찾았으므로 해당 인덱스를 반환한다
            return m
        }
    }
    // 목표 원소를 찾지 못했으므로 -1을 반환한다
    return -1
}

binary_search.js

/* 이진 탐색(왼쪽 끝은 포함하고 오른쪽 끝은 제외하는 구간) */
function binarySearchLCRO(nums, target) {
    // 왼쪽 끝만 포함하는 구간 [0, n)을 초기화한다. i는 배열의 첫 원소를, j는 마지막 원소 바로 다음 위치를 가리킨다
    let i = 0,
        j = nums.length;
    // 반복하다 탐색 구간이 비면 종료한다(i = j이면 빈 구간이다)
    while (i < j) {
        // 중간 인덱스 m을 계산하며, parseInt()로 소수 부분을 버린다
        const m = parseInt(i + (j - i) / 2);
        if (nums[m] < target)
            // 이 경우 target은 구간 [m+1, j)에 있다
            i = m + 1;
        else if (nums[m] > target)
            // 이 경우 target은 구간 [i, m)에 있다
            j = m;
        // 목표 원소를 찾았으므로 해당 인덱스를 반환한다
        else return m;
    }
    // 목표 원소를 찾지 못했으므로 -1을 반환한다
    return -1;
}

binary_search.ts

/* 이진 탐색(왼쪽 끝은 포함하고 오른쪽 끝은 제외하는 구간) */
function binarySearchLCRO(nums: number[], target: number): number {
    // 왼쪽 끝만 포함하는 구간 [0, n)을 초기화한다. i는 배열의 첫 원소를, j는 마지막 원소 바로 다음 위치를 가리킨다
    let i = 0,
        j = nums.length;
    // 반복하다 탐색 구간이 비면 종료한다(i = j이면 빈 구간이다)
    while (i < j) {
        // 중간 인덱스 m을 계산한다
        const m = Math.floor(i + (j - i) / 2);
        if (nums[m] < target) {
            // 이 경우 target은 구간 [m+1, j)에 있다
            i = m + 1;
        } else if (nums[m] > target) {
            // 이 경우 target은 구간 [i, m)에 있다
            j = m;
        } else {
            // 목표 원소를 찾았으므로 해당 인덱스를 반환한다
            return m;
        }
    }
    return -1; // 목표 원소를 찾지 못했으므로 -1을 반환한다
}

binary_search.dart

/* 이진 탐색(왼쪽 끝은 포함하고 오른쪽 끝은 제외하는 구간) */
int binarySearchLCRO(List<int> nums, int target) {
  // 왼쪽 끝만 포함하는 구간 [0, n)을 초기화한다. i는 배열의 첫 원소를, j는 마지막 원소 바로 다음 위치를 가리킨다
  int i = 0, j = nums.length;
  // 반복하다 탐색 구간이 비면 종료한다(i = j이면 빈 구간이다)
  while (i < j) {
    int m = i + (j - i) ~/ 2; // 중간 인덱스 m을 계산한다
    if (nums[m] < target) {
      // 이 경우 target은 구간 [m+1, j)에 있다
      i = m + 1;
    } else if (nums[m] > target) {
      // 이 경우 target은 구간 [i, m)에 있다
      j = m;
    } else {
      // 목표 원소를 찾았으므로 해당 인덱스를 반환한다
      return m;
    }
  }
  // 목표 원소를 찾지 못했으므로 -1을 반환한다
  return -1;
}

binary_search.rs

/* 이진 탐색(왼쪽 끝은 포함하고 오른쪽 끝은 제외하는 구간) */
fn binary_search_lcro(nums: &[i32], target: i32) -> i32 {
    // 왼쪽 끝만 포함하는 구간 [0, n)을 초기화한다. i는 배열의 첫 원소를, j는 마지막 원소 바로 다음 위치를 가리킨다
    let mut i = 0;
    let mut j = nums.len() as i32;
    // 반복하다 탐색 구간이 비면 종료한다(i = j이면 빈 구간이다)
    while i < j {
        let m = i + (j - i) / 2; // 중간 인덱스 m을 계산한다
        if nums[m as usize] < target {
            // 이 경우 target은 구간 [m+1, j)에 있다
            i = m + 1;
        } else if nums[m as usize] > target {
            // 이 경우 target은 구간 [i, m)에 있다
            j = m;
        } else {
            // 목표 원소를 찾았으므로 해당 인덱스를 반환한다
            return m;
        }
    }
    // 목표 원소를 찾지 못했으므로 -1을 반환한다
    return -1;
}

binary_search.c

/* 이진 탐색(왼쪽 끝은 포함하고 오른쪽 끝은 제외하는 구간) */
int binarySearchLCRO(int *nums, int len, int target) {
    // 왼쪽 끝만 포함하는 구간 [0, n)을 초기화한다. i는 배열의 첫 원소를, j는 마지막 원소 바로 다음 위치를 가리킨다
    int i = 0, j = len;
    // 반복하다 탐색 구간이 비면 종료한다(i = j이면 빈 구간이다)
    while (i < j) {
        int m = i + (j - i) / 2; // 중간 인덱스 m을 계산한다
        if (nums[m] < target)    // 이 경우 target은 구간 [m+1, j)에 있다
            i = m + 1;
        else if (nums[m] > target) // 이 경우 target은 구간 [i, m)에 있다
            j = m;
        else // 목표 원소를 찾았으므로 해당 인덱스를 반환한다
            return m;
    }
    // 목표 원소를 찾지 못했으므로 -1을 반환한다
    return -1;
}

binary_search.kt

/* 이진 탐색(왼쪽 끝은 포함하고 오른쪽 끝은 제외하는 구간) */
fun binarySearchLCRO(nums: IntArray, target: Int): Int {
    // 왼쪽 끝만 포함하는 구간 [0, n)을 초기화한다. i는 배열의 첫 원소를, j는 마지막 원소 바로 다음 위치를 가리킨다
    var i = 0
    var j = nums.size
    // 반복하다 탐색 구간이 비면 종료한다(i = j이면 빈 구간이다)
    while (i < j) {
        val m = i + (j - i) / 2 // 중간 인덱스 m을 계산한다
        if (nums[m] < target) // 이 경우 target은 구간 [m+1, j)에 있다
            i = m + 1
        else if (nums[m] > target) // 이 경우 target은 구간 [i, m)에 있다
            j = m
        else  // 목표 원소를 찾았으므로 해당 인덱스를 반환한다
            return m
    }
    // 목표 원소를 찾지 못했으므로 -1을 반환한다
    return -1
}

binary_search.rb

### 이진 탐색(왼쪽 끝은 포함하고 오른쪽 끝은 제외하는 구간) ###
def binary_search_lcro(nums, target)
  # 왼쪽 끝만 포함하는 구간 [0, n)을 초기화한다. i는 배열의 첫 원소를, j는 마지막 원소 바로 다음 위치를 가리킨다
  i, j = 0, nums.length

  # 반복하다 탐색 구간이 비면 종료한다(i = j이면 빈 구간이다)
  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)에 있다
    else
      return m  # 목표 원소를 찾았으므로 해당 인덱스를 반환한다
    end
  end

  -1  # 목표 원소를 찾지 못했으므로 -1을 반환한다
end

코드 시각화

전체 화면 >

아래 그림(10-3)과 같이 구간을 표현하는 방식에 따라 이진 탐색 알고리즘의 초기화, 반복 조건, 구간 축소 연산이 모두 달라진다.

'양끝이 닫힌 구간'에서는 왼쪽과 오른쪽 경계를 모두 포함하므로, 포인터 \(i\)와 \(j\)로 구간을 줄이는 연산도 대칭적이다. 실수할 가능성이 더 작으므로 일반적으로 '양끝이 닫힌 구간'으로 작성하기를 권장한다.

두 가지 구간 정의

그림 10-3 두 가지 구간 정의

10.1.2 장점과 한계¶

이진 탐색은 시간과 공간 양쪽에서 좋은 성능을 보인다.

이진 탐색은 시간 효율이 높다. 데이터가 많을수록 로그 시간 복잡도의 이점이 뚜렷하다. 예를 들어 데이터 크기가 \(n = 2^{20}\)이면 선형 탐색은 \(2^{20} = 1048576\) 번 반복해야 하지만, 이진 탐색은 \(\log_2 2^{20} = 20\) 번이면 된다.
이진 탐색은 추가 공간이 필요하지 않다. 해시 탐색처럼 추가 공간을 사용하는 탐색 알고리즘보다 공간을 절약한다.

하지만 이진 탐색이 모든 상황에 적합한 것은 아니다. 주요 이유는 다음과 같다.

이진 탐색은 정렬된 데이터에만 적용할 수 있다. 입력이 정렬되지 않았다면 이진 탐색만을 위해 정렬하는 것은 오히려 손해다. 정렬 알고리즘의 시간 복잡도는 보통 \(O(n \log n)\)으로 선형 탐색과 이진 탐색보다 높기 때문이다. 원소를 자주 삽입하는 상황에서도 정렬 상태를 유지하려면 특정 위치에 삽입해야 하므로, \(O(n)\)의 큰 시간 비용이 든다.
이진 탐색은 배열에만 적합하다. 원소를 건너뛰며(연속적이지 않게) 접근해야 하는데, 연결 리스트에서는 이런 접근이 비효율적이다. 따라서 연결 리스트나 연결 리스트 기반 자료 구조에는 적합하지 않다.
데이터가 적을 때는 선형 탐색의 성능이 더 좋다. 선형 탐색은 매번 비교 1회만 필요하지만, 이진 탐색은 덧셈 1회, 나눗셈 1회, 비교 1 ~ 3회, 덧셈(뺄셈) 1회로 총 4 ~ 6회의 기본 연산이 필요하다. 따라서 데이터 수 \(n\)이 작으면 선형 탐색이 오히려 더 빠르다.

10.1 이진 탐색¶

10.1.1 구간 표현 방법¶

10.1.2 장점과 한계¶

댓글로 의견이나 질문, 제안을 남겨 주세요