👨🏻‍💻iOS 공부/Swift_CS공부

[Swift] Binary Search란?

728x90
반응형

Binary Search란 배열에서 원하는 값을 찾기위한 방법 중 하나로, Linear Search와는 차이가 있다.

뜬금없이 Linear Search는 무엇이고? Binary Search란 무엇일까?

 

먼저 Linear Search를 이해하기 위해 간단한 예시를 통해 이해해보자.

만약 아래 배열에서 "20"이란 값을 찾고 싶다면 어떻게 찾을 수 있을까?

[1,40,7,22,33,20,10,29,25,30,17,5]

보통 사람이라면 가장 좌측에서부터 하나하나 값을 봐가며, 내가 원하는 값인지 비교해 나아가는 경우가 많다.

0번째 요소인 1은 아니기에 패스, 1번째 요소인 40은 또 아니니 패스 ... 쭉 진행하며 찾는 방식이다.

 

[1,40,7,22,33,20,10,29,25,30,17,5]
 ->            *

이처럼 가장 처음부터 값을 찾아나가는 방식을 Linear Search라고 한다.

 

배열의 길이가 이렇게 짧을 때에는 금방 값을 찾을 수 있지만, 만약에 배열의 길이가 1만개라고 한다면 처음부터 값을 비교하며 찾으면

어떻게 될까..?

 

말 그대로 값을 하나하나 비교해가며 봐야하기에 O(n)의 시간이 소요되게 될 것 이다.

Linear Search의 구동 방식을 코드로 확인해보고 더 이해해보자.

func linearSearch<T:Equatable>(_ array: [T], _ object: T) -> Int? {
    for (index, obj) in array.enumerated() where obj == T {
        return index
    }
    return nil
}

먼저 T에 대해 비교하기 위해 Equatable이라는 프로토콜을 채택한다.

우리가 값들을 == 또는 !=로 비교할 수 있는 것은 데이터 타입들이 Equatable 프로토콜을 따르고 있기 때문이기에, 위 Linear Search에서도 값 비교를 위해 해당 프로토콜을 채택해준다!

 

우리가 찾고자 하는 값을 T, 탐색 대상 배열을 [T]로 봤을 때, 리턴값은 Int?로 옵셔널이 된다.

왜 옵셔널이냐하면 해당 배열에 원하는 값이 없는(nil) 경우가 발생할 수 있기 때문이다.

 

그리고 [T]의 파라미터(매개변수)인 array에 enumerated() 메서드를 적용하여 각 값에 대해 인덱스 값을 매겨준다.

이와 동시에 각 index에 해당하는 array 배열 내 요소들이 타겟 T와 같은지 비교한다.

만약 같다면 그 때의 index 값을 리턴시켜 어느 위치에 원하는 값이 존재하는지 알 수 있게 되는 것이다.

 

이전에 봤던 것 처럼, Linear Search 방식의 경우 배열의 크기탐색 속도정비례하기 때문에 배열이 커지게 된다면 그렇게 좋은 방식은 아니게 된다.

 

그래서 더 나은 방식으로 채택되는 것이 Binary Search이다.

하나의 예시로 Binary Search를 간단하게 먼저 이해해보자.

 

어렸을 때, 지금은 잘 사용하지 않는 두꺼운 전화번호부를 본 적이 있을 것이다. 전화번호부는 ㄱ부터 ㅎ까지 순서대로 나열되어 있다. 만약 1,000장인 전화번호부가 있다고 생각해보자. 여기서 "정"씨 성을 가진 사람의 번호를 찾고 싶을 때, 어떻게 해야 빠르게 찾을 수 있을까?

(정씨를 찾기 이전에 먼저 ㅈ을 찾아보자!)

 

이전의 Linear Search라면 1페이지부터 무식하게 정독했을 것이다. 하지만 Binary Search 같은 경우는, 먼저 전화번호부의 중간 위치를 피고 값을 비교하며 상황을 본다. ㄱㄴㄷㄹㅁㅂㅅㅇㅈㅊㅋㅌㅍㅎ의 순서로 있으니, 중간을 핀다면 ㅅ의 성을 가진 사람들의 리스트들이 나올 것이다.

 

자, 이제 여기서 값들의 순서에 기반하여 값의 위치를 추론하게 된다. ㅅ은 ㅈ보다 앞 순서에 해당하기 때문에, ㅅ을 포함한 앞의 절반의 전화번호부 내용은 필요가 없어진다. 왜냐하면 원하는 정보는 해당 페이지에 없기 때문이다. 그렇기에 과감하게 앞의 절반을 뜯어서 버려도 된다.

 

벌써부터 Linear Search와 출발점 자체가 다르게 된다! 이미 앞의 절반을 뜯어 버렸기 때문에 그 만큼 시간을 절약할 수 있게 된다.

하지만 아직 원하는 값을 찾은 것이 아니기 때문에, 위 방법을 계속적으로 진행한다.

 

이제 손에 들고 있는 전화번호부는 ㅇㅈㅊㅋㅌㅍㅎ로 이루어져 있다. 여기서 다시 절반을 펼치게 되면, ㅊ이 나오게 된다.

그렇다면 다시, ㅊ은 ㅈ보다 앞 순서에 해당하는가? 아니다. ㅊ은 ㅈ보다 뒤에 있어야 하기 때문에 다시 과감하게 뒷부분인 ㅊㅋㅌㅍㅎ은 버려도 된다. 그렇게 되면 ㅇㅈ많이 남게 되고, 다시 절반을 피면 ㅇ이 나오게 되고, 동일한 방식으로 ㅇ을 버리고 ㅈ으로 시작하는 리스트를 얻을 수 있게 된다!

 

무언가 편안한 상황에서 너무 딱 떨어지는 것 같은 기분이 들텐데...

무엇 때문일까 생각해보면 배열이 이미 "정렬"되어 있었다는 것을 알 수 있다. 

 

만약 배열이 정렬이 되어있지 않고 무작위로 위치해 있었다면 어땠을까?

아마 순서를 따지지 못해서 값을 제대로 찾지 못하고 헤맬 가능성이 높다. 

 

Binary Search정렬된 배열을 대상으로 사용 가능하기에, 정렬은 필수적인 선행요소이다.

 

어? 그렇다면 Linear Search에 비해 "정렬"이라는 추가 task가 생겨서 더 느려질 수 도 있지 않나요??

그럴 수 있다. 정말 간단한 문제라면 간단한 Linear Search가 좀 더 빠를 수 있다. 다만 Binary Search의 경우는 배열을 한 번만 정렬하고, 해당 배열 내의 여러 키워드를 찾고자 할 때 매우 유용하게 사용된다. 정렬만 한 번 해두면 원하는 값을 더 빠르게 찾을 수 있기 때문이다.

 

이에 Binary Search의 경우는 O(log n)의 성능을 보인다. 

배열의 길이가 길어지더라도 Linear Search와는 다르게, 신속하게 값을 찾아낼 수 있다. 

 

이제 실제 값들과 코드를 통해 이해해보자. 

 

먼저 앞서 사용했던 배열을 정렬하면 아래와 같은 순서로 정리가 된다. 

[1,5,7,10,17,20,22,25,29,30,33,40]



정렬은 되었으니 이제 코드를 봐보자. 

 

func binarySearch<T: Comparable>(_ a : [T], key: T, range: Range<Int>) -> Int? {
	if range.lowerBound >= range.upperBound {
    	// 원하는 값이 배열에 없는 상황이다. 
    	return nil
        
    } else {
    	let midIndex = range.lowerBound + (range.upperBound - range.lowerBound) / 2
		
        if a[midIndex] > key { 
        	// 중간을 포함한 뒤의 배열 버림
        	return binarySearch(a, key = key, range = range.lowerBound ..< midIndex)
        } else if a[midIndex] < key {
        	// 중간을 포함한 앞의 배열 버림 
        	return binarySearch(a, key = key, range = midIndex + 1 ..< range.upperBound)
        } else { 
        	// 바로 중간에 위치한 값이었을 경우
        	return midIndex
}

먼저 이번에는 Equatable 프로토콜이 아닌 Comparable을 채택하고 있다. Comparable은 Equatable을 상속받는 프로토콜로 <, <=, >=, 그리고 > 비교연산을 가능하게 해준다.  

 

그리고 range를 통해 우리가 버리게 될, 살리게 될 범위를 지정할 수 있도록 한다. 

 

먼저 range의 최솟값이 최댓값을 넘는 경우는 우리가 찾는 값이 없다는 것과 같기에 nil을 반환한다. 

이에 아래의 케이스들을 하나씩 봐보면 일전에 예시를 통해 봤던 것 처럼 가장 먼저 midIndex를 구한다. 

 

그리고 원하는 값의 위치와 비교하며, 앞을 버릴지, 뒤를 버릴지 정하게 된다. 

return 값 내에 다시 binarySearch를 사용하여 재귀적으로 구현하게 된다. 

a[midIndex] 값이 key보다 크거나, 작을 때 모두 midIndex 값을 제거해주기 위해 범위를 제어해주고 있는 것을 확인할 수 있다. 

 

자 아까 정렬해두었던 배열을 가지고 생각해보자. 

만약 30을 찾고싶다면 어떤 순서로 값을 찾게 될까? 

[1,5,7,10,17,20,22,25,29,30,33,40]
                          * 

 

먼저 midIndex는 6으로 a[6] ( = 22) 의 값과 30을 비교해본다. ( 전화번호부와 달리 index는 0부터 시작한다는 점 주의! )

 

[1,5,7,10,17,20,22,25,29,30,33,40]
               a[6]       * 

a[6] < key의 경우에 해당하기에 앞의 배열들을 버린다. 

[x,x,x,x,x,x,x | 25,29,30,33,40]
                        * 

다시 midIndex는 2로 해당하는 값은 30이 된다. 이 경우에는 운 좋게도 바로 a[midIndex] = key의 경우이기에 바로 원하는 값을 찾게 된 것이다. 

 

두 스텝만에 원하는 값을 찾게 된 것을 보면 Binary Search가 얼마나 강력한 탐색 방법인지 확인 가능하다. 

 

다시 말하자면, 정말 간단한 문제라면 간단한 Linear Search가 좀 더 빠를 수 있다. 다만 Binary Search의 경우는 배열을 한 번만 정렬하고, 해당 배열 내의 여러 키워드를 찾고자 할 때 매우 유용하게 사용된다. 정렬만 한 번 해두면 원하는 값을 더 빠르게 찾을 수 있기에 효율적이다!

 

이렇게 Linear Search와 Binary Search에 대해 알아보았다. 

이제 정보 탐색을 위해, 배열의 정보를 확인하고 알맞는 알고리즘을 사용할 수 있을 것 같다!

 

 

728x90
반응형