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

 

 

 

안녕하세요 :) 소들입니다!!!!!!!

이번 포스팅은 탐색 알고리즘 중에서도,

이진 탐색 알고리즘에 대해 다뤄볼까 합니다!!! 👀

 

이전에 공부한 완전 탐색 알고리즘은, 최악의 경우 모든 배열을 순회하기 때문에,

시간 복잡도가 O(n)으로 성능이 좋은 편은 아니였어요 :)

이진 탐색은 완전 탐색보다 좋은 성능을 자랑한답니다 하하하ㅏㅎ

 

그럼 어떻게 탐색하길래 성능이 좋아진 것인지.. 알아보러 갑시다 💩

 모든 포스팅은 편의 말투로 합니다~!!

 

 

 

 

1. 이진 탐색이 모야?

 

이진 탐색은 어떤 알고리즘이냐면,

 

탐색할 자료를 둘로 나누어, 해당 데이터가 있을 곳을 탐색함

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

 

오.. 정의는 뭔 🐶소린가 싶겠지만,

여기서 중요한 것은 "둘로 나누어"와, "정렬되어 있는 자료만 가능"이란 것임!!!

예시로 보면 이또한 매우매우 쉬움 :)

 

만약 다음과 같이 오름차순으로 정렬된 배열이 있을때,

 

 

 

 

우리가 35란 데이터를 이진 탐색으로 찾는다고 하면,

가장 먼저 mid(가운데)를 기준으로 반으로 나누는 것임

 

 

 

 

이렇게!!

그럼 이제 탐색할 데이터인 35와 mid인 20을 비교함!

아 참고로 배열 갯수가 홀수, 짝수인 것과 상관 없이, (배열 갯수 / 2) 한 값이 mid의 index가 됨

 

오홍? mid 보다 35가 더 크네????

그러면 오른쪽에 나눠진 데이터를 기준으로 위 작업을 또 반복하는 것임

(이렇게 때문에 정렬되어 있을 경우에만 사용 가능한 것임!! 오른쪽엔 mid 보다 큰 값들만 들어있을테니!!)

만약 mid 보다 35가 더 작으면 왼쪽에 나눠진 데이터를 기준으로 반복했을 것이고,

mid가 35일 경우, 이땐 원하는 값을 찾은 것이니 true를 리턴하면 됨 👀

 

 

 

 

 

이렇게 또 가운데를 mid로 정하고 왼쪽, 오른쪽으로 나눈 뒤, mid와 35을 비교함

 

오홍? mid 보다 35가 더 크네???

그럼 오른쪽에 나눠진 데이터로 위 작업을 또 반복하는 것임 :)

 

근데, 오른쪽에 데이터가 1개만 남았으니, 이땐 나누는 작업을 더이상 반복하지 않고,

남은 데이터와 탐색하려는 데이터 35를 비교해서, 같으면 true, 다르면 false를 리턴하면 됨!!

아하..! 이를 보아 느껴지는 거 있음?

 

mid를 찾고 반으로 나누는 것을 재귀 함수로 구현하면 쉽겠구나..!

탈출 조건은 입력으로 들어온 배열의 데이터가 1개 남았을 때구나!

(물론 재귀 말고 반복문으로도 짤 수 있어서, 반복문 코드도 첨부해 놓겠습니당)

 

아이 쉽다~~ 🌝

자, 이제 코드로 짜봅시다 :)

 

 

 

 

2. 코드로 구현 해보기

 

 

// 재귀 함수로 구현하기
func binarySearch(_ array: [Int], num: Int) -> Bool {
    if array.count == 1 {
        return array[0] == num ? true : false
    }
    let mid = array.count / 2
    if array[mid] == num { return true }
    let range = array[mid] > num ? (0..<mid) : ((mid + 1)..<array.count)
    
    return binarySearch(Array(array[range]), num: num)
}

 

// 반복문으로 구현하기
func binarySearch(_ array: [Int], num: Int) -> Bool {
    var start = 0
    var end = (array.count - 1)
    
    while start <= end {
        let mid = (start + end) / 2
        
        if array[mid] == num { return true }
        if array[mid] > num {
            end = mid - 1
        } else {
            start = mid + 1
        }
    }
    return false
}

 

 

재귀만으로 구현 해봤는데 ... 보통 반복문으로도 많이 구현하는 것 같아서

반복문으로 구현한 코드도 추가 했습니당 :)

 

 

 

 

3. 이진 탐색의 시간 복잡도

 

n개의 배열을 매번 2로 나누어, (최악의 경우) 배열의 갯수가 1이 될 때까지 반복하니,

이진 탐색의 시간 복잡도는

 

O(𝑙𝑜𝑔𝑛)

 

이 되는 것임 :)

완전 탐색보다 훨 성능이 좋아졌꾼!! 다음 짤을 보면 더 이해하기 쉬울 것임

 

 

출처 : https://blog.penjee.com/binary-vs-linear-search-animated-gifs/

 

 

 

.

.

.

이진 탐색 알고리즘 포스팅 끝 :)

이진 탐색 트리와 비교해보면 매우 쉬운 알고리즘이라 생각해서...!!

혹시 궁금점 피드백은 언제나 댓글 주세용 🌝