[Algorithm] 이진탐색 (Binary Search) (Swift)

이진탐색

알고리즘을 풀다보면 특정 조건을 만족하는 해를 찾아야 하는 경우가 있는데 이 경우 유용한 알고리즘이 이진탐색이다. 물론 데이터가 오름차순, 내림차순으로 정렬되어있는 경우, 어떠한 기준에 의하여 순서가 정해져 있는 경우에만 사용이 가능하다.

 

원리를 아주 간단하게 요약하자면 계속 반토막 내면서 탐색범위를 줄여나가는 것이라고 생각하면 쉽다. 그리고 확인하는 것은 탐색범위의 중간값이다. 따라서 시간복잡도는 아래의 식에 의해서 O(logN)이다. (log2 상수는 무시된다)

 

이진탐색 과정

이진탐색은 다음과 같은 과정을 거친다. 인덱스를 기준으로 low를 왼쪽의 맨 끝, high를 오른쪽의 맨 끝으로 정하고 시작한다. 그 low, high의 중간을 mid로 둔 뒤, mid에 있는 값을 검색한다. 임의로 여기서는 찾으려는 값이 29라고 생각해보자. 그렇다면 중간값의 값은 19로 원하는 값보다 작기 때문에 low를 조정해준다.

아래와 같이 low를 mid+1로 조정한뒤 새로운 mid를 다시 검색한다. 찾으려는 값이 29이기 때문에 high를 정해준다.

high를 mid-1로 조정해주고, 다시 mid를 검색한다. 그렇게 검색한 값이 원하는 29값이 되었기 때문에 탐색을 종료한다.

 

아래의 GIF를 보면서 이해하면 쉽다. Sequential serach(시퀸스 탐색)의 경우 11번의 탐색으로 37을 찾지만 Binary search의 경우 3번의 탐색으로 아주빠르게 37을 찾을 수 있다.

 

출처: https://www.mathwarehouse.com/programming/gifs.php#binlinsearch

위의 gif를 아래의 코드로 바꿔보았다.

func binarySearch(_ array: [Int], _ target: Int) -> Int {
    var low = 0
    var high = array.count-1
        
    while low <= high {
        let mid = (low + high) / 2
        if array[mid] == target { return mid }
        if array[mid] > target {
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    
    return low
}

print(binarySearch([1,3,5,7,11,13,17,19,23,29,31,37,41,43,47], 11)) // 4