[Swift + Algorithm] 이진탐색이란?

작성일 : 2023-04-07

이진탐색이란 ?

이진 탐색은 이미 정렬된 리스트에서 원하는 값을 찾는 데에 사용되는 검색 알고리즘입니다. 이진 탐색은 divide-and-conquer(분할 정복) 전략을 사용하여 리스트를 반으로 나누고, 찾고자 하는 값과 중간값을 비교하여 해당 값이 중간값보다 작으면 왼쪽 반에서 탐색을 계속하고, 크면 오른쪽 반에서 탐색을 계속합니다. 이러한 과정을 반복하면서 원하는 값이 나올 때까지 계속 반으로 나누어 찾아가는 것입니다.

이진 탐색은 최악의 경우에도 O(log n)의 시간 복잡도를 가지므로 매우 효율적인 검색 알고리즘 중 하나입니다. 하지만 리스트가 정렬되어 있어야 하고, 새로운 값을 추가할 때마다 리스트를 다시 정렬해야 하므로 삽입/삭제 연산에는 적합하지 않습니다.

이진 탐색 코드 구현(Swift)


swift
func binarySearch<T: Comparable>(_ array: [T], key: T) -> Int? {
    var lowerBound = 0
    var upperBound = array.count - 1

    while lowerBound <= upperBound {
        let midIndex = (lowerBound + upperBound) / 2
        let midValue = array[midIndex]

        if midValue == key {
            return midIndex
        } else if midValue < key {
            lowerBound = midIndex + 1
        } else {
            upperBound = midIndex - 1
        }
    }

    return nil
}

위 코드에서는 제네릭(Generic)을 사용하여 모든 타입의 배열에서 이진 탐색을 할 수 있도록 구현하였습니다. 함수의 인자로는 배열과 찾고자 하는 값이 들어갑니다. 함수 내부에서는 lowerBound와 upperBound 변수를 사용하여 검색 범위를 설정하고, while 루프를 통해 중간값을 계속해서 찾아가며 탐색을 진행합니다. 찾고자 하는 값과 중간값을 비교하여 검색 범위를 좁혀나가다가, 원하는 값이 나올 경우 해당 인덱스를 반환하고, 값이 없을 경우 nil을 반환합니다.

참고

🔗 "Comparable Protocol 이란 ?" 글 참고

비교가 가능한 protocol이며 대표적으로 아래의 type들이 Comparable protocol을 준수하고 있습니다.

Int, UInt, Double, Float, CGFloat

String, Character

재귀함수로 작성

아래 함수는 그래프의 인접 리스트와 시작 노드를 인자로 받아, BFS를 수행하고 방문한 노드를 출력합니다.


swift
func binarySearch2<T: Comparable>(_ array: [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 array[midIndex] > key {
            return binarySearch(array, key: key, range: range.lowerBound..<midIndex)
        } else if array[midIndex] < key {
            return binarySearch(array, key: key, range: midIndex+1..<range.upperBound)
        } else {
            return midIndex
        }
    }
}

이진 탐색으로 풀 수 있는 문제.

특정 값의 존재 여부를 확인하는 문제: 이진 탐색은 정렬된 배열에서 특정 값의 위치를 빠르게 찾아내므로, 배열에 특정 값이 존재하는지 여부를 빠르게 확인할 수 있습니다.
가장 가까운 값 찾기 문제: 이진 탐색을 이용하여 특정 값과 가장 가까운 값의 위치를 찾을 수 있습니다.
범위 검색 문제: 이진 탐색을 이용하여 배열에서 특정 범위에 속하는 값들을 빠르게 찾을 수 있습니다.
최대, 최소 값 찾기 문제: 이진 탐색을 이용하여 배열에서 최대값과 최소값을 빠르게 찾을 수 있습니다.
자신이 원하는 값을 찾을 때까지 탐색하는 문제: 이진 탐색은 자신이 원하는 값을 찾을 때까지 반복적으로 탐색을 수행하는데, 이러한 방식은 이진 탐색을 이용한 다양한 문제에서 유용하게 활용됩니다.

[Swift + Algorithm] 이진탐색이란?

[Swift + Algorithm] 이진탐색이란?

이진탐색이란 ?

이진 탐색 코드 구현(Swift)

재귀함수로 작성

이진 탐색으로 풀 수 있는 문제.

기타 및 참고 자료