이진 검색(Binary Search)

[최종 수정일 : 2017.05.24]

원문 : https://github.com/raywenderlich/swift-algorithm-club/tree/master/Binary%20Search

이진 검색(Binary Search)

목표 : 배열에서 요소를 빨리 찾습니다.

배열에 숫자가 있고 배열에 특정 숫자가 있는지와 인덱스 위치를 확인하려한다고 가정해 봅니다.

대부분의 경우, Swift의 indexOf() 함수는 충분히 좋습니다.

let numbers = [11, 59, 3, 2, 53, 17, 31, 7, 19, 67, 47, 13, 37, 61, 29, 43, 5, 41, 23]

numbers.indexOf(43)  // returns 15

내장된 indexOf() 함수는 선형 검색(linear search)을 수행합니다. 코드는 다음과 같습니다.

func linearSearch<T: Equatable>(_ a: [T], _ key: T) -> Int? {
    for i in 0 ..< a.count {
        if a[i] == key {
            return i
        }
    }
    return nil
}

그리고 다음과 같이 사용합니다.

linearSearch(numbers, 43)  // returns 15

뭐가 문제인가요? linearSearch()은 찾고자 하는 요소를 찾을때까지, 처음부터 배열 전체를 반복합니다. 최악의 경우, 배열내의 값은 없고 모든 작업은 아무것도 수행하지 않습니다.

평균적으로, 선형 검색 알고리즘은 배열의 값 절반을 조사해야 합니다. 배열이 충분히 큰 경우에, 이것은 매우 느리게 시작합니다.

분할하고 차지하기(Divide and conquer)

속도를 빠르게 하는 고전적인 방법은 바이너리 검색(binary search)을 사용하는 것입니다. 그 비결(trick)은 값을 찾을때까지 배열을 반으로 나누는 것입니다.

n크기의 배열에 대해, 성능이 선형(linear) 검색처럼 O(n)이 아니라 O(log n)입니다. 상황을 고려해서, 1,000,000 개의 요소가 있는 배열의 이진 검색은log_2(1,000,000) = 19.9이기 때문에, 찾고자 하는 것을 찾기 위해서 20단계가 걸립니다. 그리고 수십억개의 요소가 있는 배열에서는 30단계가 걸립니다. (한편으로는, 마지막으로 10억개 요소의 배열을 사용한게 언제인가요?)

멋지게 들리지만, 이진 검색을 사용할때 단점이 있습니다. : 배열이 반드시 정렬되어 있어야 합니다. 실제로 이것은 문제가되지 않습니다.

이진 검색 동작 방법은 다음과 같습니다.

• 배열의 절반을 나누고 찾고자 하는 것이 검색(search) 키 왼쪽에 있는지 오른쪽에 있는지 확인합니다.
• 검색 키의 절반을 어떻게 결정하나요? 이 때문에 배열을 먼저 정렬했으므로 간단하게 <나 >로 비교할 수 있습니다.
• 검색 키가 왼쪽 절반에 있다면, 그쪽을 반복해서 처리합니다. : 왼쪽 절반을 두개로 나누고 검색키가 어디에 있는지 확인합니다(오른쪽 절반에 있을때에도 마찬가지입니다)
• 검색 키가 발견될때까지 반복합니다. 배열을 더 이상 나눌수 없을때, 유감스럽지만 배열내에 검색키가 없다는 결론을 내려야 합니다.

이제 왜 이진 검색이라 불리는지 알것입니다. : 모든 단계에서 배열을 절반으로 나눕니다. 분해하고 차지하기(divide-and conquer) 는 검색 키가 있어야 하는 위치를 빠르게 좁힐수 있습니다.

코드(The code)

Swift에서 이진 겁색을 재귀적으로 구현하는 방법은 다음과 같습니다.

func binarySearch<T: Comparable>(_ a: [T], key: T, range: Range<Int>) -> Int? {
    if range.lowerBound >= range.upperBound {
        // If we get here, then the search key is not present in the array.
        return nil

    } else {
        // Calculate where to split the array.
        let midIndex = range.lowerBound + (range.upperBound - range.lowerBound) / 2

        // Is the search key in the left half?
        if a[midIndex] > key {
            return binarySearch(a, key: key, range: range.lowerBound ..< midIndex)

        // Is the search key in the right half?
        } else if a[midIndex] < key {
            return binarySearch(a, key: key, range: midIndex + 1 ..< range.upperBound)

        // If we get here, then we've found the search key!
        } else {
            return midIndex
        }
    }
}

이것을 시험해 보려면 플레이그라운드에 코드를 복사하고 해보세요

let numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67]

binarySearch(numbers, key: 43, range: 0 ..< numbers.count)  // gives 13

numbers 배열이 정렬되어 있다는 것을 주의합니다. 그렇지 않으면 이진검색 알고리즘은 작동하지 않습니다.

이진 검색은 배열을 절반으로 나눠서 작동한다고 했지만, 실제로 두개의 배열을 만드는 것은 아닙니다. 대신에, Swift의 Range 객체를 사용해서 이러한 분할을 추적합니다. 초기에는 배열의 전체 범위를 포함한 0..<numbers.count입니다. 배열을 분할 할때 범위는 점점 더 작아집니다.

주의
알고 있어야 할 한가지는 range.upperBound가 항상 마지막 요소 다음 하나를 가리킨다는 것입니다. 예제에서, 배열내에 19개의 숫자들이 있기 때문에 범위는 0..<19이고 range.lowerBound = 0이고 range.upperBound = 19입니다. 하지만 시작 우리 배열의 마지막 요소는 0부터 시작하기 때문에 19번째 인덱스가 아닌 18번째 인덱스에 있습니다. 범위를 사용할때 이 점을 명심하세요. : upperBound는 언제나 마지막 요소 인덱스보다 하나 많습니다.

예제 따라가기(Stepping through the example)

알고리즘이 어떻게 동작하는지 자세히 보는 것이 유용할 수 있습니다.

위의 배열은 19개의 숫자로 구성되며 정렬할때 다음과 같습니다.

[ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67 ]

배열에 숫자 43이 있는지 확인하려고 합니다.

배열을 반으로 분할하려면, 우리는 중간에 있는 객체의 인덱스를 알아야 합니다. 이것은 다음 줄에 의해 결정됩니다.

let midIndex = range.lowerBound + (range.upperBound - range.lowerBound) / 2

처음에는 lowerBound = 0과 upperBound = 19 범위를 가집니다. 이러한 값들을 채우면, midIndex는 0 + (19 - 0)/2 = 19/2 = 9 입니다. 실제로 9.5이지만 정수를 사용하기에 반올림이 됩니다.

다음 그림에서 *는 중간 항목을 보여줍니다. 보시다시피, 각 부분에 있는 항목의 수는 동일하며, 중간에서 오른쪽으로 분리됩니다.

[ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67 ]
                                  *

이제 이진 검색은 사용할 절반을 결정할 것입니다. 코드에서 관련 섹션은 다음과 같습니다.

if a[midIndex] > key {
    // use left half
} else if a[midIndex] < key {
    // use right half
} else {
    return midIndex
}

이 경우에, a[midIndex] = 29입니다. 검색 키보다 작기 때문에, 검색키가 배열의 왼쪽 절반에 없다는 결론을 내릴수 있습니다. 따라서 검색키는 오른쪽 절반 어디에 있어야 합니다(또는 배열에 없습니다).

이제 이진 검색을 간단하게 반복할 수 있지만, midIndex + 1에서 range.upperBound까지의 배열 간격입니다.

[ x, x, x, x, x, x, x, x, x, x | 31, 37, 41, 43, 47, 53, 59, 61, 67 ]

배열의 왼쪽 절반에 대해서 더 이상 신경 쓸 필요가 없기 때문에, x로 표시했습니다. 이제 오른쪽 절반만 볼것이며, 배열 인덱스 10에서 시작합니다.

새로운 중간 요소의 인덱스를 계산합니다 : midIndex = 10 + (19 - 10)/2 = 14이고 배열을 가운데로 다시 나눕니다.

[ x, x, x, x, x, x, x, x, x, x | 31, 37, 41, 43, 47, 53, 59, 61, 67 ]
                                                 *

보다시피, a[14]는 실제로(indeed) 배열의 오른쪽 절반의 중간 요소입니다.

검색 키가 a[14]보다 크거나 작은가요? 그것은 43 < 47이기 때문에 작습니다. 이번에는 왼쪽 절반을 가지고 오른쪽의 큰 숫자들은 무시합니다.

[ x, x, x, x, x, x, x, x, x, x | 31, 37, 41, 43 | x, x, x, x, x ]

새로운 midIndex는 다음과 같습니다:

[ x, x, x, x, x, x, x, x, x, x | 31, 37, 41, 43 | x, x, x, x, x ]
                                     *

이 검색 키는 37보다 크며, 오른쪽 부분으로 계속합니다.

[ x, x, x, x, x, x, x, x, x, x | x, x | 41, 43 | x, x, x, x, x ]
                                        *

다시 한번, 검색키가 크므로, 한번 더 분리하고 오른쪽을 가집니다.

[ x, x, x, x, x, x, x, x, x, x | x, x | x | 43 | x, x, x, x, x ]
                                            *

이제 끝났습니다. 검색 키는 우리가 보고 있는 요소와 같으며, 마침내 우리가 찾고 있는 것을 발견했습니다. 숫자 43은 배열 인덱스 13에 있습니다.

많은 일이 있는 것처럼 보이지만, log_2(19) = 4.23이며, 실제로 배열에서 검색키를 찾는데 4단계만 걸렸습니다. 선형 검색으로는 14단계가 걸립니다.

43대신 42를 검색하면 어떻게 되나요? 이 경우에, 배열을 더 이상 나눌수 없습니다. range.upperBound는 range.lowerBound보다 작아집니다. 이 알고리즘은 검색키가 배열에 없으면 nil을 반환합니다.

주의
이진 검색의 많은 구현은 midIndex = (lowerBound + upperBound) / 2을 계산합니다. 여기에서 lowerBound + upperBound가 정수가 수용할 수 있는 최대 숫자를 오버플로우(overflow) 할 수 있기 때문에, 매우 큰 배열에만 나타나는 미묘한(subtle) 버그가 있습니다. 이러한 상황은 64비트 CPU에서는 발생하지 않을 것이지만, 32비트 기계에서는 확실히 가능합니다.

반복 vs 재귀(Iterative vs recursive)

이진 검색은 동일한 논리를 반복적으로 작은 하위배열에 적용하기 때문에, 본질적으로 재귀적입니다. 하지만, binarySearch()를 재귀함수로 구현해야 하는 것을 의미하지는 않습니다. 반복적인 함수 호출 대신에 간단한 반복문을 사용하여 재귀 알고리즘을 반복(iterative) 버젼으로 변환하는것이 종종 더 효율적입니다.

Swift에서 이진 검색을 반복(iterative)으로 구현하는 방법은 다음과 같습니다.

func binarySearch<T: Comparable>(_ a: [T], key: T) -> Int? {
    var lowerBound = 0
    var upperBound = a.count
    while lowerBound < upperBound {
        let midIndex = lowerBound + (upperBound - lowerBound) / 2
        if a[midIndex] == key {
            return midIndex
        } else if a[midIndex] < key {
            lowerBound = midIndex + 1
        } else {
            upperBound = midIndex
        }
    }
    return nil
}

보다시피, 이 코드는 재귀 버전과 매우 비슷합니다. 주요 차이점은 while 반복문을 사용하는 것입니다.

그것은 다음과 같이 사용합니다.

let numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67]

binarySearch(numbers, key: 43)  // gives 13

끝(The end)

배열을 먼저 정렬해야 하는 것이 문제인가요? 그렇습니다. 정렬하는데 시간이 필요합니다 - 이진 검색과 정렬을 결합하면 간단한 선형 검색을 하는 것보다 느릴수 있습니다. 이진 검색은 한번만 정렬한 다음에 많은 검색을 하는 상황에서 뛰어납니다(shines).