Algorithm) 이진 탐색(Binary Search) in Swift

이진탐색에 대해 알아보자.

 

오랜만에 프랑스어 단어 'incroyable' 를 찾기 위해서 종이사전을 꺼냈다.

여러번 종이 사전으로 단어를 찾아본 경험이 있지 않더라도, 알파벳 순서는 정렬되어있기 때문에

자연스레 사전을 절반으로 갈라서 펼치는 내 자신을 보았다.

아!!! 여기서 나는 이진 탐색(Binary search)을 나도 모르게 하고 있었음을 깨달았다.

 

위의 에피소드에서 중요한 내용이 나왔다.

바로 이진 탐색을 하기 위해선 주어진 무엇인가가 정렬(사전은 A,B,C,D 순서로..)되어 있어야 한다는 것이다.

쉽게 생각해서 사전이 abcd 순서로 되어있지 않다면 반을 펼치는 것이 무슨 의미가 있겠는가? 펼쳤는데 A가 나온다면... (절레절레)

 

이러한 이진 탐색은 주어진 배열에 원하는 원소가 있으면 그 원소를 반환하는 것이 아니고

그 원소의 ‘위치’ 를 반환한다. 그렇지 않다면 nil 을 반환하겠지?

 

이처럼 중간을 활용하는 알고리즘이 바로 이진 탐색이다.

이 이진 탐색은 숫자가 클수록 그 위력을 발휘하는데, 단순탐색과 비교하면 이해가 빠르다.

 

1부터 1024까지의 숫자가 있다고 치자. 그리고 1024의 숫자를 찾고자 한다.

 

단순 탐색을 사용한다면 1부터 1024까지.... 1024번의 탐색을 해야한다.

Oh my goodness... 나는 탐색하지 않을 것이다.

이처럼 모든 원소를 한번씩 건드리게 되는 경우를 빅오 표기법으로 'O(n)' 의  시간이 걸린다고 이야기 한다.

 

이진 탐색으로 똑같은 경우에 1024 를 찾는다고 치자.

자 일단 중간값인 512 를 선택했다. 내가 찾는 경우는 이보다 크니 512 보다 작은 경우는 필요 없다!!! 한번의 검색으로

1~512가 사라지는 Magic.

 

자 이제 513~1024 사이에서 또 중간값 대략 768 을 확인하고 1024와 비교.

513~768이 사라지는 Magic.

 

이런 식으로 총 10번의 비교를 통해 찾는 값 1024를 찾게 된다.

 

이는 숫자가 커지면 커질수록 이진 탐색의 장점이 드러나는데

만약 숫자가 100,000,000 일 경우 단순 탐색은 1억번의 검색을 해야하는 반면 이진 탐색은 음... 

갑자기 계산 귀차니즘 발생.. 아무튼 20번 내로 탐색이 완료된다.

이러한 이진 검색의 시간은 빅오 표기법으로 'O(log n)' 이 걸린다고 표시한다.

log n ? n ? 빅오 표기법은 잘 모르겠지만 아무튼 'O(log n)' 이 'O(n)' 보다 빠른거구나 라고만 알고 있어도 오늘의 목적은 달성이다.

 

이제 이진 검색에 대해서 어느 정도 감이 오게 되었다.

그럼 이제 스위프트로 구현해보자.

 

일단, 함수의 Parameter 로는 무엇을 받아야 할까?

바로 '정렬이 되어있는 배열' 과 '내가 찾는 숫자' 여야 한다.

이를 'array' 와 'num' 으로 하겠다.

 

그 다음은 배열의 '시작' 과 배열의 '끝', 배열의 '중간' 을 저장할 변수가 필요하다.

이를 각각 'start' 와 'end' 와 'mid' 로 하겠다.

 

배열의 중간 인덱스의 '값' 을 저장할 변수가 필요하다.

이를 'value' 로 하겠다.

 

let sampleArray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

func binarySearch(array: [Int], num: Int) -> Int? {
    
    var start = 0
    var end = array.count - 1
    
    while start <= end { // 이게 false 가 되는 경우는 둘이 만나는, 그러니까 배열의 원소가 1개만 남는 경우.
        
        let mid = (start + end) / 2
        let value = array[mid]
        
        if value == num {
            return mid                // 값이 아닌 위치를 반환한다.
        } else if value > num {       // 내가 찾는 숫자보다 추측 값이 더 큰 경우 => 다음에는 더 작게 추측해야한다.
            end = mid - 1
        } else {                      // 숫자가 추측 값보다 더 큰 경우 => 다음에는 더 크게 추측해야한다.
            start = mid + 1
        }

    }
    
    return nil
}

binarySearch(array: sampleArray, num: 13) // Result : 12
binarySearch(array: sampleArray, num: 16) // Result : Nil

 

티스토리 코드블록이 글을 작성할때는 잘 나오는데 막상 피시로 다시 보면 다 깨져서 스샷도 올려봅니다..

 

 

이진 검색 끝!