Binary Search (이진 탐색)

Binary Search (이진 탐색)

---

정렬 등과 함께 쓰이는 기초적인 알고리즘으로, 큰 리스트를 두 부분으로 나누고 탐색의 범위를 나눠진 리스트 중 하나에서만 찾아감으로서 범위를 좁히는 알고리즘 기법이다.

 

보통 start mid end 라는 세 개의 변수를 두고, mid값을 기준으로 리스트를 나눈 뒤, 크다면 mid값을 start로, 작은 부분에 속한다면 mid값을 end로 두고 탐색의 범위를 좁힌다.

 

코틀린은 binarySearch라는 라이브러리 함수를 지원한다.

fun main() {
    val arr = IntArray(100) {it} // (1,2,3,4 ... 100)

    // 50을 찾는 경우
    println(arr.binarySearch(50))  // 출력: 50

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

 

출력되는 값은 찾는 원소의 인덱스 값을 출력해준다.

다만, 찾는 원소가 없다면 - (원래 있어야 할 위치의  인덱스) -1 을 리턴하게 된다.

위 예제를 통해 알아보면, 50은 50번째 인덱스이므로 50을 리턴하게 되고, -1의 경우 원래 있어야할 0번째 -1 이되어 -1을 리턴하게 된다.

 

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

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

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

    return -1
}