[Algorithm/Swift] 이진 탐색(Binary Search)

안녕하세요 제인입니다 :)

오늘은 탐색 알고리즘 중 이진 탐색(Binary Search)이 무엇인지 알아보고 Swift 코드로 구현까지 해보려고 합니다.

이진 탐색 알고리즘의 경우 탐색의 범위가 아주 큰 상황에서 속도를 내서 탐색할 수 있는 방법이니 잘 정리해두면 유용하게 사용할 수 있을 것 같습니다. 바로 시작해볼게요!

이진 탐색이란?

먼저, 이진 탐색이 왜 필요할까요?? 리스트 내에서 원하는 데이터를 찾기 위해 가장 기본적인 탐색 방법인 순차 탐색 방법과 비교하며 이진 탐색을 사용해야 하는 이유에 대해 알아봅시다.

순차 탐색

순차 탐색이란 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법입니다.

보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용하게 됩니다. 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 데이터를 찾을 수 있다는 장점이 있습니다. 

또한, 순차 탐색은 가장 앞에 있는 원소부터 하나씩 차례로 확인하며 데이터를 찾는 방법이므로 데이터 정렬 여부와 상관없이 항상 사용할 수 있으며 반복문으로 매우 쉽게 구현할 수 있다는 장점도 있습니다.

하지만, 데이터의 개수가 N개 일 때 최대 N번의 비교 연산이 필요하므로 최악의 경우 시간 복잡도는 O(N)입니다. 그렇기 때문에 탐색의 범위가 아주 큰 상황이라면 단순히 앞에서 부터 하나씩 비교해나가는 방법은 시간이 매우 많이 소요될 수 있으므로 더 효율적인 탐색 방법이 필요합니다!

이진 탐색

이제 순차 탐색보다 훨씬 더 효율적인 탐색 방법인 이진 탐색에 대해 알아봅시다.

이진 탐색은 탐색의 범위를 절반씩 좁혀가며 데이터를 탐색하는 탐색 방법입니다. 단, 리스트 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘입니다. 따라서 데이터가 무작위일 때는 사용할 수 없지만, 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있다는 특징이 있습니다.

 

이진 탐색은 반으로 쪼개며 탐색하는 방법이기 때문에 시작점, 끝점, 중간점 이렇게 위치를 나타내는 변수 3개를 사용해서 탐색을 진행합니다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾아나가는 것이 이진 탐색의 과정입니다.

이진 탐색 그림으로 이해하기

이진 탐색을 그림으로 쉽게 이해해봅시다. 이미 정렬된 10개의 데이터 중 값이 4인 원소를 찾는 예시로 살펴볼게요!

시작점, 끝점, 중간점을 정하는 것으로 탐색을 시작합니다.

시작점은 0, 끝점은 마지막 인덱스인 9로 정하고, 리스트의 인덱스가 Int 타입이기 때문에 중간점은 4.5에서 소수점을 버려서 4로 정합니다. 다음으로, 중간점의 값과 찾고자 하는 값을 비교합니다. 현재, 위의 그림에서 확인할 수 있듯이 중간점의 값인 8보다 찾고자 하는 값인 4가 더 작습니다. 그렇다면 이제 중간점 이후의 값들은 확인하지 않아도 되는 값들이 되겠죠? (정렬된 데이터이기 때문에 중간점의 값보다 큰 값들임이 보장되어있음) 이를 이용해서 다음 탐색을 진행하기 위해 다시 시작점, 끝점, 중간점을 세팅합니다.

이제 새로운 끝점은 이전 탐색에서 확인한 값인 8 바로 이전의 값이 됩니다. 시작점은 그대로 0이 되고, 중간점은 시작점과 끝점의 중앙값인 1(1.5에서 소수점을 버린 값)이 됩니다. 그런 다음, 중간점의 값과 찾아야 하는 값을 비교해보면 이번에는 중간점의 값인 2보다 찾고자 하는 값인 4가 더 큰 값입니다. 그렇다면 이제 중간점 이전의 값들은 제외해도 되는 값들이 됩니다!

이전 탐색에서 중간점이었던 인덱스 바로 뒤인 2를 시작점으로 새로 세팅하고 끝점은 3 그대로 두게 되면 중간점은 시작점과 같은 2(2.5에서 소수점을 버린 값)가 됩니다. 중간점의 값과 찾고자 하는 값을 비교하면 이번에는 일치하므로 여기서 탐색이 종료됩니다!

 

전체 데이터의 개수는 10개지만, 이진 탐색을 이용해 총 3번의 탐색으로 원소를 찾을 수 있었습니다. 위의 예시의 경우 순차 탐색을 이용해도 3번의 탐색으로 원하는 데이터를 찾을 수 있겠지만, 훨씬 넓은 범위에서 탐색을 하게 될 경우 순차 탐색보다 훨씬 효율적으로 탐색할 수 있을 것입니다. 이진 탐색은 한 번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어든다는 점에서 시간 복잡도가 O(logN)입니다.

Swift 코드로 구현하기

위의 예시에서 알 수 있듯이 이진 탐색은 위치를 나타내는 변수 세팅, 중간값과 비교 라는 과정이 계속 반복되는 방식이기 때문에 재귀함수, 반복문 이렇게 두가지 방법으로 구현할 수 있습니다. 하나씩 살펴봅시다!

 

// 재귀 함수로 구현하기
func binarySearch(_ array: [Int], num: Int) -> Int {
    if array.count == 1 { // 배열 크기 1인 경우
        return array[0] == num ? 0 : -1
    }
    // 배열 크기 1이상이라면
    let mid = array.count / 2  // 중간점
    if array[mid] == num { return mid } // 찾으려는 값 찾은 경우 중간점 인덱스 리턴
    // 중간점 값이 찾으려는 값보다 큰 경우 -> 탐색 범위를 0~중간점-1까지
    // 중간점 값이 찾으려는 값보다 작은 경우 -> 탐색 범위를 중간점+1~끝까지로 다시 설정
    let range = array[mid] > num ? (0..<mid) : ((mid + 1)..<array.count)
    
    return binarySearch(Array(array[range]), num: num)
}

 

// 반복문으로 구현하기
func binarySearch(_ array: [Int], num: Int) -> Int {
    var start = 0 // 시작점
    var end = (array.count - 1) // 끝점
    
    while start <= end {
        let mid = (start + end) / 2 // 중간점
        
        if array[mid] == num { return mid } // 찾은 경우 중간점 인덱스 반환
        if array[mid] > num { // 찾으려는 값보다 중간점이 더 큰 경우 -> 중간점 이후 데이터 확인 필요 x
            end = mid - 1 // 끝점을 중간점-1로 옮긴다
        } else { // 찾으려는 값보다 중간점이 더 작은 경우 -> 중간점 이전 데이터 확인 필요 x
            start = mid + 1 // 시작점을 중간점+1로 옮긴다
        }
    }
    return -1
}

 

binarySearch()는 파라미터로 탐색해야 할 배열과 찾고자하는 값을 넘겨 받는 함수이고, 찾고자 하는 값이 배열 안에 존재하는 경우 해당 값의 인덱스를 찾아서 리턴하고 존재하지 않는 경우 인덱스로 나올 수 없는 값인 -1을 리턴하게 됩니다.

위에서 그림으로 살펴본 과정을 다시 떠올려보며 주석과 함께 코드를 읽어보면 쉽게 이해가 되실 것 같습니다!

---

[참고 자료]

Swift) 탐색 :: 이진 탐색(Binary Search) 이해하기

<이것이 코딩 테스트다 with 파이썬>

이것이 취업을 위한 코딩 테스트다 with 파이썬 | 나동빈 - 교보문고