[Swift] Swift로 Binary Search( 이진 탐색 알고리즘 )를 구현해보자

1) Simple Search ( 단순탐색 ) -  시간복잡도 0(n) 

 

배열의 처음부터 하나하나씩 비교하면서 찾는 방법.
n개의 원소를 가진 리스트에서 Simple Search를 사용하면 최대 n 번의 search가 필요할 수 도 있다


2) Binary Search ( 이진 탐색 ) - 시간복잡도 O(logn)  

Simple Search와 달리, 절반씩 제외시키면서 찾는다
n개의 원소를 가진 리스트에서 Binary Search를 사용하면 최대 log2(n) 번만에 답을 찾을 수 있다 

예를 들어, 리스트에 숫자가 8개 있다면

1) Simple Search - 최악의 경우 최대 8개의 숫자 확인

2) Binary Search - 최악의 경우 최대 log2(8) = 3개의 숫자확인 

 

하는 것이다. 

ex) 리스트에 숫자가 8개 있다면

1) Simple Search - 최악의 경우 최대 8개의 숫자 확인
2) Binary Search - 최악의 경우 최대 log2(8) = 3개의 숫자확인 

 

 

배열의 특정한 아이템을 찾기 위해서 쓰는 firstIndex(of:) 연산자는 Simple Search여서 시간복잡도가 O(n) 이라고 문서에 나와있다

Complexity: O(n), where n is the length of the collection.

https://developer.apple.com/documentation/swift/array/2994720-firstindex 

firstIndex(of:) - Array | Apple Developer Documentation

 

이진 탐색을 하면 더 빠르게 인덱스를 찾아줄 것이다~~ 

// 오름차순으로 정렬된 array에서 item의 index를 return 해준다. array에 item이 없으면 -1을 리턴
func binarySearchForAscending<T: Comparable>(array: [T], item: T) -> Int {
    var low = 0
    var high = array.count - 1
    
    while low <= high {
        let mid = (low + high) / 2
        let guess = array[mid]
        if guess == item {
            return mid
        } else if guess > item {
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    
    return -1
}

// 내림차순으로 정렬된 array에서 item의 index를 return 해준다. array에 item이 없으면 -1을 리턴
func binarySearchForDescending<T: Comparable>(array: [T], item: T) -> Int {
    var low = 0
    var high = array.count - 1
    
    while low <= high {
        let mid = (low + high) / 2
        let guess = array[mid]
        if guess == item {
            return mid
        } else if guess < item {
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    
    return -1
}