PHpullh
학습 라이브러리/Kotlin/이진 검색 (Binary Search)

KOTLIN · 컬렉션

이진 검색 (Binary Search)

정렬된 리스트에서 binarySearch로 효율적으로 원소를 검색합니다. O(log n) 시간 복잡도를 보장합니다.

컬렉션고급binary-searchsortedsearchlog-n

핵심 설명

정렬된 리스트에서 binarySearch로 효율적으로 원소를 검색합니다. O(log n) 시간 복잡도를 보장합니다.

Kotlin code

fun main() {
    val sorted = listOf(2, 5, 8, 12, 16, 23, 38, 56, 72, 91)

    // 기본 이진 검색
    val index = sorted.binarySearch(23)
    println("23의 위치: $index")  // 5

    // 찾지 못한 경우: -(삽입 지점) - 1
    val notFound = sorted.binarySearch(20)
    println("20 검색 결과: $notFound")        // 음수
    val insertionPoint = -(notFound + 1)
    println("20 삽입 지점: $insertionPoint")  // 5

    // 객체 이진 검색
    data class Product(val name: String, val price: Int)
    val products = listOf(
        Product("사과", 1000),
        Product("바나나", 2000),
        Product("체리", 5000),
    )
    val found = products.binarySearch {
        it.price.compareTo(2000)
    }
    println("가격 2000: ${products[found].name}")

    // 범위 검색
    val range = sorted.binarySearch(10)
    println("10 이상 시작 인덱스: ${-(range + 1)}")
}

학습 팁

이진 검색의 반환값이 음수면 -(result + 1)이 삽입 지점입니다. 이를 활용하여 범위 검색도 가능합니다.

주의할 점

binarySearch는 리스트가 정렬되어 있어야 합니다. 정렬되지 않은 리스트에서 호출하면 잘못된 결과를 반환합니다.

자주 묻는 질문

이진 검색 (Binary Search)란 무엇인가요?

정렬된 리스트에서 binarySearch 로 효율적으로 원소를 검색합니다. O(log n) 시간 복잡도를 보장합니다.

이진 검색 (Binary Search) 학습 시 주의할 점은 무엇인가요?

binarySearch 는 리스트가 정렬되어 있어야 합니다. 정렬되지 않은 리스트에서 호출하면 잘못된 결과를 반환합니다.