목표: 배열에서 특정 요소를 빠르게 찾는다.
숫자 배열이 있고, 특정 숫자가 배열에 있는지, 있다면 어떤 인덱스에 있는지 확인하려고 한다.
대부분의 경우 Swift의 Collection.index(of:) 함수로 충분하다:
let numbers = [11, 59, 3, 2, 53, 17, 31, 7, 19, 67, 47, 13, 37, 61, 29, 43, 5, 41, 23]
numbers.index(of: 43) // 15를 반환기본 제공 Collection.index(of:) 함수는 선형 탐색을 수행한다. 코드로 표현하면 다음과 같다:
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) // 15를 반환그렇다면 문제는 무엇인가? linearSearch()는 배열의 처음부터 끝까지 순회하며 찾고자 하는 요소를 탐색한다. 최악의 경우, 값이 배열에 없으면 모든 작업이 무의미하게 된다.
평균적으로 선형 탐색 알고리즘은 배열의 절반 값을 확인해야 한다. 배열이 충분히 크면 이 과정이 매우 느려진다!
이 과정을 빠르게 하는 전통적인 방법은 이진 탐색을 사용하는 것이다. 핵심은 배열을 반으로 나누어가며 원하는 값을 찾을 때까지 반복하는 것이다.
크기가 n인 배열에서 성능은 선형 탐색의 **O(n)**이 아니라 **O(log n)**이다. 이를 쉽게 설명하자면, 1,000,000개의 요소를 가진 배열에서 이진 탐색은 약 20번의 단계만으로 원하는 값을 찾을 수 있다. 왜냐하면 log_2(1,000,000) = 19.9이기 때문이다. 그리고 10억 개의 요소를 가진 배열에서는 단 30번의 단계면 충분하다. (그런데, 마지막으로 10억 개의 배열을 사용한 적이 언제였는가?)
이진 탐색은 훌륭하지만 한 가지 단점이 있다: 배열이 정렬되어 있어야 한다. 실제로는 이 문제가 크게 걸림돌이 되지는 않는다.
이진 탐색이 어떻게 동작하는지 살펴보자:
< 또는 > 비교를 통해 위치를 확인할 수 있다.이제 왜 "이진" 탐색이라고 부르는지 알 것이다: 각 단계에서 배열을 두 개의 절반으로 나누기 때문이다. 이 분할 정복 과정을 통해 탐색 키의 위치를 빠르게 좁혀나갈 수 있다.
다음은 Swift로 구현한 이진 탐색의 재귀 버전이다:
func binarySearch<T: Comparable>(_ a: [T], key: T, range: Range<Int>) -> Int? {
if range.lowerBound >= range.upperBound {
// 탐색 키가 배열에 없을 경우
return nil
} else {
// 배열을 나눌 위치 계산
let midIndex = range.lowerBound + (range.upperBound - range.lowerBound) / 2
// 탐색 키가 왼쪽 절반에 있는지 확인
if a[midIndex] > key {
return binarySearch(a, key: key, range: range.lowerBound ..< midIndex)
// 탐색 키가 오른쪽 절반에 있는지 확인
} else if a[midIndex] < key {
return binarySearch(a, key: key, range: midIndex + 1 ..< range.upperBound)
// 탐색 키를 찾은 경우
} 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) // 결과: 13numbers 배열이 정렬되어 있다는 점에 주의한다. 이진 탐색 알고리즘은 정렬된 배열에서만 동작한다.
이진 탐색은 배열을 반으로 나누는 방식으로 동작하지만, 실제로 두 개의 새로운 배열을 생성하지는 않는다. 대신 Swift의 Range 객체를 사용해 배열의 범위를 추적한다. 처음에는 이 범위가 전체 배열을 포함하지만, 배열을 나눌수록 범위가 점점 작아진다.
참고:
range.upperBound는 항상 마지막 요소의 다음 위치를 가리킨다. 예를 들어, 배열에 19개의 숫자가 있으므로 범위는0..<19이다. 따라서range.lowerBound = 0이고range.upperBound = 19이다. 하지만 배열의 마지막 요소는 인덱스 18에 위치한다. 범위를 다룰 때 이 점을 명심해야 한다:upperBound는 항상 마지막 요소의 인덱스보다 1이 크다.
알고리즘이 어떻게 동작하는지 자세히 살펴보면 도움이 된다.
위 예제에서 사용한 배열은 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처음에 range.lowerBound = 0이고 range.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 {
// 왼쪽 절반 사용
} else if a[midIndex] < key {
// 오른쪽 절반 사용
} else {
return midIndex
}이 경우 a[midIndex] = 29이다. 이는 탐색 키보다 작으므로, 탐색 키가 왼쪽 절반에 있을 수 없다는 결론을 내릴 수 있다. 왼쪽 절반에는 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]는 배열 오른쪽 절반의 중간 요소이다.
탐색 키가 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에 있다. w00t!
많은 작업처럼 보일 수 있지만, 실제로는 배열에서 탐색 키를 찾는 데 네 단계만 걸렸다. 이는 log_2(19) = 4.23이므로 적절하다. 선형 탐색을 사용했다면 14단계가 걸렸을 것이다.
43 대신 42를 탐색한다면 어떻게 될까? 이 경우 배열을 더 이상 나눌 수 없다. range.upperBound가 range.lowerBound보다 작아지고, 이는 탐색 키가 배열에 없다는 것을 의미한다. 알고리즘은 nil을 반환한다.
참고: 많은 이진 탐색 구현에서
midIndex = (lowerBound + upperBound) / 2를 계산한다. 이는 매우 큰 배열에서만 나타나는 미묘한 버그를 포함한다.lowerBound + upperBound가 정수가 가질 수 있는 최대값을 초과할 수 있기 때문이다. 이 상황은 64비트 CPU에서는 발생하기 어렵지만, 32비트 머신에서는 확실히 발생할 수 있다.
이진 탐색은 기본적으로 재귀적이다. 동일한 로직을 점점 작아지는 하위 배열에 반복적으로 적용하기 때문이다. 그러나 반드시 binarySearch()를 재귀 함수로 구현해야 하는 것은 아니다. 재귀 알고리즘을 반복 버전으로 변환하는 것이 더 효율적일 때가 많다. 이 경우 여러 번의 재귀 함수 호출 대신 간단한 루프를 사용한다.
다음은 Swift로 구현한 반복 방식의 이진 탐색 예제다:
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) // 13을 반환배열을 먼저 정렬해야 하는 것이 문제일까? 상황에 따라 다르다. 정렬에 시간이 걸린다는 점을 명심해야 한다. 이진 탐색과 정렬을 함께 사용하면 단순한 선형 탐색보다 느릴 수 있다. 이진 탐색은 한 번 정렬한 후 여러 번 탐색을 수행할 때 빛을 발한다.
더 알아보려면 위키백과를 참고한다.
Swift Algorithm Club을 위해 Matthijs Hollemans가 작성