이분 탐색 (Binary Search)

배열의 중간 요소를 반복적으로 확인하며 탐색 범위를 절반으로 줄여나갑니다. 시간 복잡도는 아래와 같습니다.

작동 원리

1. 정렬된 데이터: 이분 탐색은 반드시 정렬된 데이터에서만 동작합니다.
2. 중간 값 선택: 배열의 중간 값을 선택합니다.
3. 조건 비교:
   • 찾는 값이 중간 값보다 작으면 왼쪽 절반을 탐색합니다.
   • 찾는 값이 중간 값보다 크면 오른쪽 절반을 탐색합니다.
   • 찾는 값이 중간 값과 같으면 탐색을 종료합니다.
4. 반복: 값을 찾거나 범위가 비워질 때까지 반복합니다.

fun binarySearch(array: IntArray, target: Int): Int {
    var low = 0
    var high = array.size - 1

    while (low <= high) {
        val mid = low + (high - low) / 2 // 중간 인덱스 계산

        when {
            array[mid] == target -> return mid // 값을 찾은 경우
            array[mid] < target -> low = mid + 1 // 오른쪽 절반 탐색
            else -> high = mid - 1 // 왼쪽 절반 탐색
        }
    }

    return -1 // 값을 찾지 못한 경우
}

위와 같은 알고리즘으로 동작하게 됩니다.

실제 백준 문제 중 하나를 풀어보겠습니다.

https://www.acmicpc.net/problem/1920

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

이분 탐색 알고리즘을 활용하여 하나의 리스트를 for 문을 돌며 각 원소의 존재 유무를 확인할 수 있습니다.

fun main() {
    // 입력
    val n = readLine()!!.toInt()
    val arrayA = readLine()!!.split(" ").map { it.toInt() }.sorted() // 정렬된 배열
    val m = readLine()!!.toInt()
    val arrayB = readLine()!!.split(" ").map { it.toInt() }

    // 이분 탐색 함수
    fun binarySearch(array: List<Int>, target: Int): Boolean {
        var low = 0
        var high = array.size - 1

        while (low <= high) {
            val mid = (low + high) / 2
            when {
                array[mid] == target -> return true // 찾았음
                array[mid] < target -> low = mid + 1 // 오른쪽 탐색
                else -> high = mid - 1 // 왼쪽 탐색
            }
        }
        return false // 없음
    }

    // 배열 B의 각 원소에 대해 A에서 탐색
    val result = arrayB.map { if (binarySearch(arrayA, it)) 1 else 0 }

    // 출력
    result.forEach { println(it) }
}