[알고리즘]이진 탐색

테이블이 킷값을 기준으로 정렬되어 있다면 이진 탐색(binary search)이라는 보다 효율적인 알고리즘을 사용할 수 있다.

이것은 한 번 비교할 때마다 탐색 범위가 절반으로 줄어들기 때문에 '이진'이란 이름이 붙었다.

테이블의 모든 레코드가 킷값의 오름차순으로 정렬되어 있다고 가정해보자.

이진 탐색은 먼저 테이블의 중앙에 있는 레코드를 탐색 키와 비교한다.

 

1. 만약 중앙 레코드의 킷값이 탐색 키와 같으면 탐색은 성공한 것이고, 중앙 레코드의 위치(인덱스)를 반환하면 된다.

2. 중앙 레코드가 탐색 키보다 크면 그보다 오른쪽에 있는 모든 레코드는 탐색 키보다 크므로 더는 탐색할 필요가 없다.

3. 중앙 레코드가 탐색 키보다 작으면 오른쪽만 탐색하면 된다.

 

이렇게 이진 탐색에서는 단계마다 검색해야 할 레코드의 수가 반으로 줄어든다.

동작을 좀 더 구체적으로 살표보자.

위 그림은 정렬된 배열에서 이진 탐색으로 27을 찾는 과정이다.

남은 탐색의 범위를 나타내는 low와 high 및 중앙 위치를 나타내는 middle을 사용한다.

 

1. 최초의 탐색 범위는 low=0, high=15 이다.
   중앙 위치 middle=7을 계산하고, 이 위치의 킷값(25)이 탐색 키(27) 보다 작으므로
   low~middle 사이에는 27이 없는 것이 확실하다.
   이제 low는 middle+1이 되고, 반으로 줄어든 범위(low~high)에 다시 탐색을 진행한다.
2. 새로 계산한 middle 위치의 값(A[11]=36)이 탐색 키보다 크다. 따라서 오른쪽인 middle~high 사이에는 탐색 키가 없다.
   이제 high는 middle-1이고, 반으로 줄어든 범위에서 다시 탐색을 진행한다.
3. middle 위치의 값(31)이 킷값보다 크다. 따라서 high가 middle-1이 된다.
4. middle 위치의 값(27)이 탐색 키와 같다. 따라서 탐색은 성공하고, middle 위치의 8을 반환한다.

우리는 이미 일상생활에서 이진 탐색을 많이 사용하고 있다.

예를 들어, 사전에서 단어를 찾는 과정이 이진 탐색인데,

사전을 펼쳐 찾고자 하는 단어가 현재 페이지보다 앞에 있는지 뒤에 있는지를 확인하고

단어가 있는 부분만을 다시 탐색해 탐색 범위를 줄인다.

 

 

# 이진 탐색 알고리즘(순환 구조)

이진 탐색은 알고리즘 자체가 순환적이기 때문에 다음과 같이 순환 호출을 이용하여 기술하는 것이 쉽다.

// 이진 탐색 알고리즘(순환 구조)

function binary_search(A, key, low, high) {
	if(low <= high) { // 항목들이 남아 있으면(종료 조건)
    	middle = ~~((low+high)/2); // middle 계산, 실수가 아닌 정수여야 하기 때문에 ~~를 사용
        if(key == A[middle]) { // 탐색 성공
        	return middle; // 중앙 레코드의 인덱스 반환
        } else if(key < A[middle]) { // 왼쪽 부분리스트 탐색 -> 순환호출)
        	return binary_search(A, key, low, middle-1);
        } else { // 오른쪽 부분리스트 탐색 -> 순환호출
        	return binary_search(A, key, middle+1, high);
        }
    return -1; // 탐색 실패 -1 반환
}

 

# 이진 탐색 알고리즘(반복 구조)

// 이진 탐색 알고리즘(반복 구조)

function binary_search_iter(A, key, low, high) {
	while(low <= high) { // 항목들이 남아 있으면(종료 조건)
    	middle = ~~((low+high)/2); // middle 계산, 실수가 아닌 정수여야 하기 때문에 ~~를 사용
        if(key == A[middle]) { // 탐색 성공
        	return middle; // 중앙 레코드의 인덱스 반환
        } else if(key > A[middle]) { // key가 middle의 값보다 크면
        	low = middle + 1; // middle+1 ~ high 사이를 검색
        } else { // key가 middle의 값보다 작으면
        	high = middle - 1; // low ~ middle-1 사이 검색
        }
    return -1; // 탐색 실패 -1 반환
}

 

 

# 이진 탐색은 얼마나 빠를까?

이진 탐색은 매 단계에서 탐색 범위가 반으로 줄어드는 것을 알 수 있었다.

만약 테이블의 크기 n이 2의 거듭제곱인 2^k라고 가정하면, 순환 호출을 한번 할 때마다 탐색 범위가 다음과 같이 줄어든다.

 

2^k  ➡️ 2^(k-1) ➡️ 2^(k-2) ➡️ ... ➡️ 2^1 ➡️ 2^0

 

단계의 수는 k에서 0까지 k+1번의 단계를 거친다.

이때 n은 2^k이므로 k=log n 이다.

따라서, 이진 탐색은 log n 에 비례하는 시간이 걸리는 O(log n) 알고리즘이다.

이것은 매우 효율적인데,

예를 들어, 10억 명이 정렬된 배열에서 순차 탐색으로 특정한 이름을 찾는다면 평균 5억 번의 비교가 필요하지만,

이진 탐색은 단지 30여 번의 비교 만에 탐색이 완료된다!

 

 

# 이진 탐색 특징

1. O(log n)의 매우 효율적인 탐색 방법이다.
2. 반드시 배열이 정렬되어 있어야 사용할 수 있다.
3. 테이블이 한번 만들어지면 이후로 변경되지 않고 탐색 연산만 처리한다면 이진 탐색이 최고의 선택 중 하나이다.

만약 테이블에 레코드를 삽입하거나 삭제하는 일이 빈번하게 일어나는 응용이라면 이야기는 약간 달라진다.

먼저 삽입을 생각해보면, 크기가 n인 테이블에 새로운 레코드를 삽입하려면

당연히 삽입 후에도 테이블의 정렬 상태가 유지되어야 하므로 삽입은 정확한 위치에서 이루어져야 한다.

따라서 먼저 레코드가 들어가야 할 위치를 찾아야 한다.

 

다음으로 그 위치에 레코드를 끼워 넣어야 하는데, 여기에도 문제가 있다.

테이블이 배열 구조라면 삽입할 위치부터 이후의 모든 레코드를 한 칸씩 뒤로 밀어야 하기 때문이다.

그리고 최악의 경우 이동해야 하는 레코드의 수는 테이블의 크기와 같은 n이다.

결국 정렬된 테이블에 레코드를 삽입하기 위해서는 n에 비례하는 시간, 즉 O(n)이 소요되는 것이다.

이것은 삭제 연산도 마찬가지이다.

삭제할 위치를 찾고, 그 위치의 레코드를 삭제하면 이후의 모든 레코드를 한 칸씩 앞으로 이동해야 한다.

 

💡 데이터의 삽입이나 삭제가 빈번한 응용에는 이진 탐색이 좋지 않다.
탐색은 효율적이지만 비효율적인 삽입과 삭제 연산이 더 많이 처리된다면 전체적으로 불리할 수 있기 때문이다.
이런 응용에서는 이진 탐색 트리와 같은 다른 방법을 사용하는 것이 좋다고 한다.

 

 

 

 

 

 

출처 : 최영규, "자료구조와 알고리즘 with 파이썬", 생능북스 p.221~225