[PS] 이진 탐색

Hood·2024년 12월 7일

Binary Search ps

PS

목록 보기

8/15

✍ Kotlin을 사용한 PS 문제 풀이를 위한 알고리즘

소속 중인 A&I 동아리에서 코딩 역량을 강화하고자
코딩캠프를 진행하며 작성한 포스트입니다.
해당 포스트는 Kotlin을 기반으로 작성하였습니다.

들어가기 전

1부터 100까지의 배열에서 77을 찾는다고 가정해 보겠습니다.
가장 단순한 방법은 1부터 차례대로 확인하면서 77이 나올 때까지 반복하는 것입니다.

이처럼 앞에서부터 하나씩 확인하는 방법을 순차 탐색(Linear Search) 이라고 합니다.
이 방식은 최악의 경우 배열의 끝까지 모두 확인해야 하므로, 시간 복잡도는

O(N)

이 됩니다.

예를 들어 데이터의 개수가 매우 많아져서
1000억 개의 숫자 중 47억 번째 근처에 있는 값을 찾아야 한다면,
순차 탐색은 그만큼 많은 비교를 수행해야 합니다.

즉, 데이터의 범위가 커질수록 순차 탐색은 비효율적일 수 있습니다.

이진 탐색

이진 탐색(Binary Search)은 정렬된 데이터에서 원하는 값을 빠르게 찾기 위한 알고리즘입니다.

이진 탐색의 핵심은
탐색 범위를 한 번에 절반씩 줄여 나간다는 점입니다.

즉,

시작점(start)과 끝점(end)을 정하고
그 중간 위치(mid)를 계산한 뒤
중간 값과 찾고자 하는 값을 비교합니다
비교 결과에 따라 절반을 버리고 다시 탐색합니다

이 과정을 반복하면
매번 절반씩 범위가 줄어들기 때문에 매우 빠르게 값을 찾을 수 있습니다.

단, 이진 탐색을 사용하려면 데이터가 반드시 정렬되어 있어야 합니다.

예를 들어봅시다

1부터 10까지의 정렬된 데이터에서 7을 찾는다고 생각해 보겠습니다.

처음에는 전체 범위를 탐색 대상으로 둡니다.

이때 중간점은 다음과 같이 계산합니다.

mid = \frac{start + end}{2}

예를 들어 인덱스를 0부터 사용한다면,

start = 0
end = 9
mid = (0 + 9) / 2 = 4

가 됩니다.

즉, 중간 인덱스는 4이고,
해당 위치의 값은 5입니다.

우리가 찾는 값은 7이므로,
5보다 큰 값이 필요합니다.
따라서 왼쪽 절반은 더 이상 볼 필요가 없고,
오른쪽 절반만 다시 탐색하면 됩니다.

다시 중간점을 계산하면,
이번에는 더 좁아진 범위 안에서 새로운 mid를 구하게 됩니다.

그리고 마찬가지로 중간 값과 7을 비교하여
필요 없는 절반은 버립니다.

이 과정을 반복하다 보면
중간 인덱스가 시작점과 같아지는 경우도 생깁니다.

결국 이진 탐색은
배열 전체를 처음부터 끝까지 확인하지 않고도
원하는 값을 빠르게 찾을 수 있습니다.

이처럼 이진 탐색은 단계마다 탐색 범위를 절반으로 줄여 나가기 때문에
시간 복잡도는

O(\log_2 N)

이 됩니다.

코딩테스트에서의 활용

코딩테스트에서는 단순히 “배열에서 특정 값을 찾는 이진 탐색”보다
매개변수 탐색(Parametric Search)의 형태로 자주 등장합니다.

매개변수 탐색이란
어떤 최적화 문제를
“이 값이 가능한가?”라는 결정 문제로 바꾼 뒤,
그 기준값을 이진 탐색으로 찾는 방법입니다.

예를 들어 다음과 같은 문제가 이에 해당합니다.

랜선을 잘라 만들 수 있는 최대 길이
예산 상한선의 최댓값
공유기 설치 간격의 최댓값

즉, 코딩테스트에서는 이진 탐색 자체보다
이진 탐색을 어디에 적용할 수 있는지 판단하는 능력이 더 중요합니다.

in Kotlin

이제 Kotlin으로 직접 구현해 보겠습니다.

재귀적 방법

이진 탐색은 재귀 함수로도 구현할 수 있습니다.

다만 재귀로 구현할 때는
탐색 범위가 더 이상 유효하지 않은 경우를 처리해야 합니다.
즉, start > end가 되면 찾는 값이 없는 것이므로 종료해야 합니다.

fun main() {
    val arr = listOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
    val result = binarySearch(arr, 7, 0, arr.size - 1)

    if (result != -1) {
        println("인덱스 $result 에 7이 있습니다.")
    } else {
        println("7을 찾지 못했습니다.")
    }
}

fun binarySearch(arr: List<Int>, target: Int, start: Int, end: Int): Int {
    if (start > end) return -1

    val mid = (start + end) / 2

    return when {
        arr[mid] == target -> mid
        arr[mid] < target -> binarySearch(arr, target, mid + 1, end)
        else -> binarySearch(arr, target, start, mid - 1)
    }
}

이 코드의 흐름은 다음과 같습니다.

시작점과 끝점을 이용해 중간점을 계산합니다.
중간 값이 찾는 값과 같다면 해당 인덱스를 반환합니다.
중간 값이 더 작다면 오른쪽 절반을 다시 탐색합니다.
중간 값이 더 크다면 왼쪽 절반을 다시 탐색합니다.
범위가 역전되면(start > end) 값이 없는 것이므로 -1을 반환합니다.

재귀 함수를 사용하지 않는 방법

재귀 대신 반복문으로도 구현할 수 있습니다.
실전에서는 반복문 방식이 더 익숙하고 안정적으로 느껴지는 경우도 많습니다.

이 경우 함수 안에서 시작점과 끝점을 직접 관리하면서
while 문으로 탐색을 진행하면 됩니다.

fun main() {
    val arr = listOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
    val result = binarySearch(arr, 7)

    if (result != -1) {
        println("인덱스 $result 에 7이 있습니다.")
    } else {
        println("7을 찾지 못했습니다.")
    }
}

fun binarySearch(arr: List<Int>, target: Int): Int {
    var start = 0
    var end = arr.size - 1

    while (start <= end) {
        val mid = (start + end) / 2

        if (arr[mid] == target) {
            return mid
        } else if (arr[mid] < target) {
            start = mid + 1
        } else {
            end = mid - 1
        }
    }

    return -1
}