이진 탐색(Binary Search)

 

1. 이진 탐색이란?

 

탐색할 자료를 둘로 나누고, 원하는 데이터를 탐색하는 알고리즘으로

탐색할 자료가 정렬이 되어 있을 때 사용이 가능함!

 

[2, 5, 9, 10, 11, 15, 20, 21]의 정렬된 배열이 있을때,

가운데를 기준으로 반으로 나눔!

 

[2, 5, 9, 10] [11, 15, 20, 21]

여기서 가운데는 배열의 갯수를 2로 나누었을 때의 index

8 / 2 = 4

 

index 4 = 11 이므로

여기서 타겟이 21이라고 하면, 11보다 크기 때문에

다시 위와 같은 작업을 반복!

 

[11, 15] [20, 21]

index = 2

가운데 값은 20이 나오고 타겟(21)이 더 크니까 또 반복하면 되는데,

남은 데이터가 1개밖에 없으니 남은 데이터와 타겟값을 비교해서 return 하면 된다.!

 

 

2. 코드로 구현

재귀로 구현

func binarySearch(array: [Int], num: Int) -> Int {
    if array.count == 1 { // 배열의 크기가 1인 경우
        return array[0] == num ? 0 : -1
    }
    
    let mid = array.count / 2 // mid
    if array[mid] == num { return mid } // target을 찾으면 return
    
    // target이 mid보다 크다면 탐색 범위는 (mid + 1) ~ 끝
    // target이 mid보다 작으면 탐색 범위는 0 ~ (mid - 1)
    let range = array[mid] > num ? (0..<mid) : ((mid + 1)..<array.count)
    return binarySearch(array: 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 {
            end = mid - 1
        } else {
            start = mid + 1
        }
    }
    return -1
}

 

 

3. 시간 복잡도

이진탐색은 배열을 매번 2로 나누어 확인할 원소의 갯수가 절반씩 줄어들고,

최악의 경우에는 배열의 갯수가 1이 될 때까지 반복하므로 시간 복잡도는 O(logN)

완전탐색의 O(n)보다는 좋은 성능을 낼 수 있다.!