티스토리 뷰

728x90
반응형

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

Declarationfunc firstIndex(of element: Element) -> Int? Available when Element conforms to Equatable. ParameterselementAn element to search for in the collection.Return ValueThe first index where element is found. If element is not found in the collection,

developer.apple.com

 

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

// 오름차순으로 정렬된 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
}
728x90
반응형
댓글
댓글쓰기 폼