코틀린 이진탐색(이분탐색, binary search)

코틀린에는 이미 이진탐색이 기본적으로 구현되어있습니다.

fun main() {
    val arr = IntArray(100) { it * 2 } // [0, 2, 4, ..., 198]

    // 찾는 원소 있을 때
    println(arr.binarySearch(100))  // 출력: 50
    println(arr.binarySearch(0))    // 출력: 0
    println(arr.binarySearch(36))   // 출력 18

    // 찾는 원소 없을 때
    println(arr.binarySearch(-5))   // 출력: -1
    println(arr.binarySearch(3))    // 출력: -3
    println(arr.binarySearch(199))  // 출력: -101
}

.binarySearch()를 통해 이진탐색을 할 수 있습니다.

본인이 알고리즘 공부용으로 이진탐색을 직접 구현하려고 한 게 아니라면 그냥 binarySearch 함수를 쓰시면 됩니다.

 

이진 탐색이므로 당연히 배열이 오름차순으로 정렬되어있어야 합니다.

찾는 원소가 존재한다면 해당 원소의 index값을 알려줍니다.

찾는 원소가 없다면 음수를 return 하는데 -(원래라면 있었어야할 위치) - 1을 리턴합니다.

예를 들어 위 arr는 [0, 2, 4, ..., 198] 이렇게 되어있기 때문에 만약 3이라는 숫자를 집어넣으려면 [2]에 집어넣어야합니다.

-(2) - 1는 -3이므로 binarySearch(3)을 하면 -3을 리턴한 모습을 알 수 있습니다.

 

왜 그냥 -2를 리턴하지 않고 굳이 - 1을 시키냐면 [0] 때문입니다.

binarySearch(-5)에서 -5는 arr의 [0]에 삽입되어야하기 때문에 -0 즉, 0을 return 해버리면 그게 [0]번째에 진짜로 -5라는 값이 있어서 0번째에 값이 있다고 리턴한 값인지, 아니면 값이 없어서 0번째에 -5가 들어가야하는 자리라고 알려준 건지 알 수가 없기 때문입니다.

 

직접 이진탐색 구현하기

fun main() {
    val arr = IntArray(100) { it } // [0, 1, 2, 3, ..., 99]

    println(arr.bSearch(191))   // 출력: -1
    println(arr.bSearch(0))     // 출력: 0
    println(arr.bSearch(-23))   // 출력: -1
    println(arr.bSearch(25))    // 출력: 25
    println(arr.bSearch(67))    // 출력: 67
}

fun IntArray.bSearch(value: Int): Int {
    var low = 0
    var high = this.lastIndex
    var mid = 0

    while (low <= high) {
        mid = (low + high) / 2

        when {
            this[mid] < value   -> low = mid + 1
            this[mid] > value   -> high = mid - 1
            this[mid] == value  -> return mid
        }
    }

    return -1
}

함수명을 IntArray.bSearch으로 정의하여 IntArray에 bSearch라는 커스텀 함수를 생성하였습니다.

이를 코틀린에서는 확장함수라고 합니다. (자바스크립트의 prototype 생각하시면 됩니다.)

 

확장 함수 내에서는 this 키워드를 통해 현재 IntArray에 접근할 수 있습니다.

값을 찾지 못한다면 무조건 -1을 출력하게 해두었습니다.

코틀린에 원래 있는 binarySearch 함수처럼 값을 찾지 못한다면 해당 값이 들어가야할 자리를 알려주게 하려면 26번째 줄에 return -1 대신 return -low - 1로 바꾸면 됩니다.

 

비트 연산(shr 1) vs 나누기 2( / 2)

위 코드의 17번째줄을 보고 "아니 이진탐색을 하는데 감히 비트 연산을 안 쓰고 나누기 2를 한단 말이야? 에잉 성능알못 ㅉㅉㅉ"라고 하실 수도 있겠습니다.

제가 학생일 때도 C언어로 이진탐색을 구현할 때, 속도를 위해 이진탐색을 할 때 나누기 2가 아니라 mid = (low + high) >> 2 이렇게 비트 시프트 연산을 사용했습니다.

하지만 자바 및 코틀린에서는 속도 차이가 없습니다.

자세한 건 다음 링크를 참고하시기 바랍니다.

 

코드라는 건 아무래도 누가봐도 이해하기 쉬운 코드를 만드는 게 우선입니다. 혼자 프로젝트하고 회사에서도 혼자 개발할 거 아니면 말이죠.

따라서 정석대로 정수 연산에서는 나누기를 비트 연산일 땐 나누기를 쓰는 게 좋다고 할 수 있겠습니다.