[알고리즘] Binary Search 이진 탐색 : 필수 기본 정리 - 장점, Kotlin 구현

목차

이진 탐색 Binary Search

이진 탐색은 가장 효율적인 탐색 알고리즘 중 하나입니다. Big O에서 O(log n)으로 나타냅니다. 균형 이진 탐색 트리(Balanced Binary Search Tree)에서 element를 찾는 것과 비슷한 구조를 가지고 있습니다. 만약 시간 복잡도와 이진 탐색 트리에 대하여 더 알고 싶으시다면 아래 링크를 확인해주세요.

[알고리즘] Binary Tree 바이너리 트리: 기본정리 - 바이너리트리 구현, 중위순회, 전위순회, 후위순

 

[알고리즘] Binary Search Tree 이진탐색 트리 : 필수기본정리 - 탐색,삽입,삭제, 검색연산, 삭제연산 -

 

우선 이진 탐색을 사용하기 위해 2가지 조건이 필요합니다. 

1. 오름차순으로 정리되어야한다.

2. 자료의 집합은 인덱스를 바꿀 때 상수 시간으로 처리되어야 합니다. Big O: (1)

 

이진 탐색 vs 선형 탐색

이진 탐색의 장점은 선형 탐색과 비교했을 때 드러납니다. 

 

먼저 ArrayList에서 선형 탐색을 때를 예를 들어보겠습니다. 아래와 같이 선형 탐색을 했을 때 indexOf()라는 method를 쓰게 되고 지정한 element를 찾을 때까지 리스트에 처음부터 끝까지 확인합니다. 

 

선형탐색에서 31를 찾기

다음으로 이진 탐색을 사용 시 장점을 보도록 하겠습니다. 31을 찾기 위해 선형 탐색에서는 8개의 element를 확인한 반면 이진 탐색에서는 3번 만에 31에 도달한 것을 확인할 수 있습니다. 

 

• STEP 1. Index의 중간값을 찾습니다. → 22가 중간값입니다. 
• STEP 2. 찾은 중간 index의 값을 확인합니다. → 찾는 값과 index의 값이 같다면 index를 리턴하고 아니면 다음 스텝으로 넘어갑니다. 
• STEP 3. 이진 탐색을 반복 실행합니다. 이진탐색 트리처럼 찾는값보다 작다면 왼쪽 찾는값보다 크다면 오른쪽으로 이동하며 값을찾습니다. 이 과정을 더이상 collection을 나눌수없을때까지 반복합니다.  

 

이진 탐색 구현

이진 탐색을 구현해보겠습니다. 

 

이진탐색 함수

//1
fun <T: Comparable<T>> ArrayList<T>.binarySearch(
	value: T,
    range: IntRange = indices //2
): Int? {
	//more to come
}

코드 설명입니다.

1. ArrayList에서 이진 탐색을 쓰기 위해 binarysearch 익스텐션을 사용해줍니다. 

2. 이진 탐색은 반복문이기때문에 얼마나 반복할지 range를 지정해줘야합니다. range는 디폴트 값을 가지고있기때문에 range를 넣어주지않아도 탐색이 실행될수있습니다. 

 

이진탐색 완성 함수

fun <T: Comparable<T>> ArrayList<T>.binarySearch(
	value: T,
    range: IntRange = indices 
): Int? {
	//1
    if (range.first > range.last){
    	return null
    }
    
    //2 
    val size = range.last - range.first + 1
    val middle = range.first + size / 2
    
    return when {
    	//3
        this[middle] == value -> middle
        //4
        this[middle] > value -> binarySearch(value, range.first until 
        middle)
        else -> binarySearch(value, (middle + 1)..range.last)
    }
    
}

코드 설명입니다. 

1. 먼저 지정된 range에 한 개 이상의 element가 있는지 확인합니다. 없다면 null을 반환합니다. 

2. range에 값이 있는 게 확인되었기 때문에 middle값을 찾습니다. 

3. 그리고 index위치에 있는 값을 찾는 값과 비교하며 탐색합니다 만약 middle index와 찾는 값이 같다면 middle index를 리턴합니다. 

4. 아니라면 왼쪽이나 오른쪽 가운데 값으로 이동하며 반복하여 찾습니다. 

 

이제 위 코드를 테스트해보겠습니다. 

"binary search" example {
	val array = arrayListOf(1, 5, 15, 17, 19, 22, 24, 31, 105, 150)
 	val search31 = array.indexOf(31)
 	val binarySearch31 = array.binarySearch(31)
 	println("indexOf(): $search31")
 	println("binarySearch(): $binarySearch31")
}

결과는 아래와 같습니다. 

---Example of binary search---
indexOf(): 7
binarySearch(): 7

이진 탐색은 인터뷰 단골 문제입니다.  만약 "Given a sorted array..." 같은 문장이 있다면 이진 탐색 알고리즘을 사용하면 됩니다.