이진 탐색 Binary Search

이진 탐색 Binary Search

목표: 배열의 원소를 빠르게 찾기

언제: 어떤 숫자들의 배열을 가졌다고 가정했을 때, 특정한 숫자가 해당 배열에 존재하는지를 알고 싶을 때

대부분의 경우, 스위프트의 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 1
    }
  }
  return nil
}

이 함수를 다음과 같이 사용할 수 있습니다.

linearSearch(numbers, 43)  // 15를 반환

무엇이 문제가 되는 걸까요? linearSearch()는 배열 전체를 시작부터 검색하여 원하는 원소를 찾을 때 까지 멈추지 않습니다. 최악의 경우에, 배열 안에 값이 없을 수도 있습니다.

평균적으로, 선형 탐색 알고리즘은 배열의 절반 정도를 탐색합니다. 배열의 크기가 크면 클수록, 느려질 것입니다.

분할과 정복 Divide and conquer

이러한 탐색을 가장 빠르게 해결하는 방법은 이진 탐색 binary search을 사용하는 것입니다. 이 알고리즘의 비결은 원하는 값을 찾을 때 까지 배열을 절반으로 나누는 것입니다.

n 만큼의 배열의 크기라면, 선형 탐색의 경우 O(n)이지만 이진 탐색은 O(log n)입니다. 더 자세히 말하자면, 1,000,000 개의 원소를 가진 배열을 이진 탐색으로 검색한다면 오로지 20 번의 탐색으로 원하는 값을 찾을 수 있다는 것입니다. 왜냐하면 log_2(1,000,000) = 19.9이기 때문입니다. 100만 건의 값에도 오로지 30 번의 탐색이면 어떤 값이든 찾을 수 있습니다.

이진탐색은 보기엔 좋아보이지만 단점 또한 가지고 있습니다. 배열이 정렬되어 있어야만 합니다. 하지만 보통의 경우엔 문제점이 되진 않습니다.

이진 탐색이 동작하는 방식은 다음과 같습니다 :

• 배열을 절반으로 나누고, 여러분이 찾는 값이 그 절반의 왼쪽에 있는지 아니면 오른쪽에 있는지를 파악하는 것입니다. 이때 여러분이 찾으려는 값을 탐색 키(search key)라고 합니다.

• 절반을 나누고나서, 어느 쪽에 탐색 키가 있는지를 판단할까요? 배열이 먼저 정렬 되어야 하는 이유가 여기에 있습니다. 단순히 <와 > 비교 연산자를 사용하면 됩니다.

• 만약 탐색키가 왼쪽 절반에 있다면, 탐색을 계속합니다. 왼쪽 절반에서 다시 절반을 나누고 탐색키가 어디에 있는지 확인합니다.

• 탐색 키를 찾을 때 까지 지금까지의 과정을 반복합니다. 배열이 더 이상 나누어지지 않는다면, 배열에 탐색 키가 존재하지 않는다는 것입니다.

이것이 "이진" 탐색이라고 불리는 이유는 모든 과정에서 배열을 절반으로 나누기 때문입니다. 탐색키가 있는 곳까지 탐색할 곳을 좁혀가므로 이것을 또한 분할과 정복이라고 합니다.

코드

스위프트로 구현한 이진 탐색을 재귀 형태로 구현하였습니다.

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: 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)  // gives 13

여기서 주의할 점은 numbers 배열은 정렬되어 있다는 것입니다. 이진 탐색 알고리즘은 정렬되지 않은 배열에서는 올바르게 동작되지 않습니다!

이진 탐색은 배열을 절반으로 분할하여 동작한다고 설명하였습니다. 하지만, 실제로 두 개의 새로운 배열을 만드는 것은 아닙니다. 대신에, 스위프트의 Range 객체를 이용하여 분할을 추적하는 것입니다. 범위를 뜻하는 range는 최초에 전체 배열을 다룹니다. 0 ..< numbers.count가 그것입니다. 배열을 분할해 나가면서, 그 범위가 점점 작아집니다.

참고 : 한 가지 주의해야 할 점은range.upperBound는 항상 마지막 원소 이후의 지점을 가리킨다는 것입니다. 이 예제에서 범위인 0..<19는 19 가지의 숫자가 배열에 있는 것을 말하므로 range.lowerBound = 0 이며, range.upperBound = 19입니다. 이 배열의 마지막 원소는 인덱스가 19가 아닌 18입니다. 프로그래밍은 항상 숫자를 0부터 셉니다. range를 다룰 때는 항상 유의하세요: upperBound는 마지막 원소의 인덱스에 하나 더 뒤로 간 것이다.

예제로 살펴보기

알고리즘이 정확히 어떻게 동작하는지를 보는 것은 중요합니다.

위 예제에서 가져온 이 배열은 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 {
  // 왼쪽 절반을 사용하라
} 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은 a[14]인 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 ]
                                        *

다시, 탐색키는 41보다 큽니다. 따라서 따라서 배열을 다시 절반으로 나누고 오른쪽을 확인합니다.

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

이제 탐색이 완료되었습니다. 탐색 키는 저희가 찾은 배열의 원소와 같습니다. 43은 인덱스 13에 있다는 결론을 내릴 수 있습니다.

탐색 과정이 많아 보이지만, 실제로는 배열에서 탐색키를 찾는 데에 4 단계 만을 밟았을 뿐입니다. 이것은 log_2(19) = 4.23입니다. 선형 검색에서는 14 단계를 밟아야 합니다.

만약 42를 찾는 것이 아닌 43을 찾아야 한다면 어떤 일이 일어 날까요? 배열을 더 이상 나눌 수 없는 상태가 되므로, range.upperBound는 range.lowerBound보다 작아지게 됩니다. 이진 탐색 알고리즘은 탐색 키가 배열에 없다는 것을 알게 되어 nil을 반환합니다.

참고: 이진 탐색을 구현한 많은 코드들이 midIndex = (lowerBound + upperBound) / 2를 사용합니다. 이것은 크기가 큰 배열에서 버그를 갖습니다. lowerBound + upperBound는 정수가 가질 수 있는 최대 값을 넘어갈 수 있습니다. 64-bit CPU에서는 해당되지 않지만, 32-bit CPU에서는 그렇습니다.

반복을 사용 vs 재귀를 사용

이진 탐색은 기본적으로 재귀입니다. 왜냐하면 동일한 로직을 배열의 더 작은 부분에서 반복적으로 적용할 수 있기 때문입니다. 하지만, binarySearch()를 반드시 재귀형 함수로 구현해야 하는 것은 아닙니다. 이진 탐색을 반복형으로 구현하는 것이 보통 더 효율적입니다.

다음은 스위프트에서 이진 탐색을 반복 함수로 구현한 것입니다.

func binarySearc<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

결론

배열이 먼저 정렬되어야 하는 것이 문제가 될까요? 정답은 상황에 따라 다르다 입니다. 정렬은 어느 정도의 시간을 요한다는 것을 명심하세요. 이진 탐색과 더불어 정렬을 하는 것은 단순히 선형 탐색을 하는 것보다 느릴 수도 있습니다. 이진 탐색은 한번의 정렬과 여러 번의 검색을 필요로 할 때 빛을 발합니다.

---

See also Wikipedia.

출처: Written for Swift Algorithm Club by Matthijs Hollemans