[알고리즘] 이진탐색 알고리즘(Binary Search)

이진 탐색(Binary Search)의 개념

이진 탐색은 정렬되어 있는 리스트 혹은 배열에서 탐색 범위를 절반씩 줄여나가며 특정 값을 찾는 알고리즘이다.

특정 범위의 숫자에서 상대가 생각한 값을 맞추는 업다운 게임을 예시로 들 수 있다.

만약 1~100이라는 범위에서 70이라는 값을 상대가 생각하고 있다고 할 때,

처음엔 50을 말하고, up이라는 반응이 나오면 50과 100의 반인 75를 말한다.

다음으로는 down이라는 반응이 나오고, 50과 75의 중간값인 62를 말한다.

이 과정을 반복해나가다보면 70이라는 값에 도달할 수 있게 된다.

 

위에서 예시로 들었던 업다운 게임은 결국 이진 탐색의 원리를 이용했다는 것을 알 수 있다.

이진 탐색의 동작 과정은 다음과 같다.

이진 탐색의 동작 과정

1. 리스트의 첫 번째 위치(left)와 마지막 위치(right)를 통해 중간위치(mid)을 알아낸다.
2. 중간값과 찾고자 하는 값을 비교한다.
   • 중간값(list[left]) < 찾고자 하는 값(list[right]) → left = mid + 1
   • 중간값(list[left]) > 찾고자 하는 값(list[right]) → right = mid - 1
   • 중간값(list[left]) = 찾고자 하는 값(list[right]) → 종료
3. 위의 과정에서 중간값 = 찾고자 하는 값일 때까지 반복한다.

이진 탐색(Binary Search) 구현

fun main() {
    val list = listOf(2, 3, 5, 10, 23, 25, 30, 49, 51)
    val target = readLine()!!.toInt()
    println(binarySearch(list, target))
}

private fun binarySearch(list: List<Int>, target: Int): Int {
    var left = 0 // 리스트의 첫 인덱스
    var right = list.size - 1 // 리스트의 마지막 인덱스

    while(left < right) {
        val mid = (left + right) / 2 // 리스트의 중간 인덱스

        if(list[mid] < target) left = mid + 1 // 찾고자 하는 값이 현재 중간 위치보다 뒤에 있으므로 left를 높여준다.
        else if(list[mid] > target) right = mid - 1 // 찾고자 하는 값이 현재 중간 위치보다 앞에 있으므로 right를 줄여준다.
        else return mid // 같으므로 현재 우치를 반환한다.
    }

    return -1 // target을 발견하지 못함.
}

결과값

                     target이 리스트에 존재                                                                                       target이 리스트에 존재 x

시간복잡도

중간을 기준으로 탐색 범위를 절반씩 줄여나가기 때문에 O(logN)의 시간복잡도를 갖는다.

Lower Bound

이진 탐색을 할 때 같은 값이 여러 개라면 어떻게 될까?

위의 코드의 리스트에 30이라는 값을 하나 더 넣고 실행시켜보았다.

6으로 나오던 인덱스가 7로 바뀐 것을 확인할 수 있다.

즉, 같은 값 중 마지막 인덱스를 반환하게 되는 것을 알 수 있다.

 

Lower Bound는 찾고자 하는 값이 리스트 내에 다수 존재할 때, 시작 값을 찾아주는 알고리즘이다.

즉, list = [2, 3, 5, 10, 23, 25, 30, 30, 30, 49, 51]이 있을 때, 30을 찾으면 6(처음 인덱스 = 0)이 나오게 된다.

우선 구현을 해보고, 이진 탐색과의 차이점을 보도록 하자.

Lower Bound 구현

fun main() {
    val list = listOf(2, 3, 5, 10, 23, 25, 30, 30, 49, 51)
    println(lowerBound(list, 30))
}

private fun lowerBound(list: List<Int>, target: Int): Int {
    var left = 0
    var right = list.size - 1

    while(left < right) {
        val mid = (left + right) / 2

        if(list[mid] < target) left = mid + 1
        else right = mid
    }

    return right
}

이진 탐색과 Lower Bound의 차이

이진 탐색에서는 찾고자 하는 값이 나왔다면 그 위치를 반환해줬었다.

하지만 Lower Bound의 코드를 보면, 찾고자 하는 값이 나오더라도 right의 값을 줄여주는 것을 확인할 수 있다.

Upper Bound

Upper Bound는 찾고자 하는 값보다 처음으로 큰 값의 위치를 찾는 알고리즘이다.

즉, list = [2, 3, 5, 10, 23, 25, 30, 30, 30, 49, 51]이고, target = 30이라 할 때 8번째 값(49)이 반환되게 된다.

Upper Bound 구현

fun main() {
    val list = listOf(2, 3, 5, 10, 23, 25, 30, 30, 49, 51)
    println(upperbound(list, 30))
}

private fun upperbound(list: List<Int>, target: Int): Int {
    var left = 0
    var right = list.size - 1

    while(left < right) {
        val mid = (left + right) / 2

        if(list[mid] <= target) left = mid + 1
        else right = mid
    }

    return right
}

이진 탐색과 Upper Bound의 차이

Upper Bound의 정의를 다시 한번 생각해보면, 우리가 찾고자 하는 target보다 처음으로 큰 값이다.

즉, target = list[mid]일 때 left의 값을 증가시켜주면 되는 것이다.