[알고리즘] 이진 검색 (Binary Search)

이진 검색(Binary Search)

 

분할 정복(Divide and Conquer)식 문제 해결방법의 대표적인 알고리즘의 하나

• 분할(Divide) : 문제를 작은 부분으로 나눈다.
• 정복(Conquer) : 나누어진 작은 문제를 해결한다.
• 그리고 해결된 문제들을 모아 최종 해답을 모은다.

정렬된 데이터를 중간값을 기준으로 2개의 영역으로  나누고 값의 범위에 따라 검색할 영역만 선택하여 검색한다.

선택적이므로 불필요한 검색이 줄어들며, 한번 영역을 선택할 때 마다 확인해야할 데이터가 2^n 만큼 줄어든다.

 

이로 인해 𝑂(log n) 로 표현할 수 있는 로그 시간의 시간 복잡도로 정의될 수 있고, 데이터의 양이 많아져도 성능의 큰 변화가 없는 장점을 가지게 됩니다.

 

장점 : 성능과 단순한 구현

단점 : 데이터가 정렬되어 있어야 한다. 정렬에 많은 시간이 소요되는 경우, 전체 실행시간에 영향 받을수 있음.

 

 

Algorithm

1. 입력 인수

• low : 데이터의 시작 index
• high : 데이터의 마지막 index
• x : 검색해야 하는 Key 값

 

2. 출력

• Key 값이 존재하는 위치 index

 

3. 수행 절차

1. 입력 데이터 index 의 중간 지점 찾기 : (low + high) / 2;
2. 중간 지점의 데이터가 Key 값과 일치하면 index 를 반환한다.
3. Key 값이 중간 지점의 데이터 보다 작으면 왼쪽 영역 ( low  ~ mid-1 ) 탐색 시작(재귀 호출)
4. Key 값이 중간 지점의 데이터 보다 크면 오른쪽 영역 ( mid+1 ~ low ) 탐색 시작(재귀 호출)
5. low 가 high 보다 크면, 찾지 못한 것이다.
6. #3 ~#5 를 나누어진 영역에서 검색 완료 후 위치 index 를 반환한다.

 

index binary_search(index low, index high, key x) {
	index mid;
    
    if( low > high )
    	return 0;
    else {
    	//! 현재 low ~ high 의 중간 지점 찾기
    	mid = (low + high)/2;
        
        //! 중간 지점이 key 값이면, index return;
        if( x == S[mid] )      
        	return mid;
        else if( x < S[mid] )  //! 왼쪽 영역(중간보다 작은, low ~ mid-1)
        	return binary_search(low, mid-1, x);
        else                   //! 오른쪽 영역(중간보다 큰, mid+1 ~ high)
        	return binary_search(mid+1, high, x);
     }    
}

 

Test Function

Test Data 는 전역으로 10개의 int 형 array 로 정의

typedef int index_t;
typedef int key_t;

const int N = 10;

int S[] = { 3, 8, 9, 11, 12, 22, 23, 31, 36, 45 };

main 함수에서는 array data 를 출력하고  36, 12, 100 을 검색하는 test 를 수행하는 코드를 넣었다.

int main(void)
{
	printf("------------------ Test Data ------------------\n");
	for (int i = 0; i < N; i++) {
		printf("[%d] %d\n", i, S[i]);
	}

	printf("-------------------- Test --------------------\n");

	int value, result;

	value = 36;
	result = binary_search(0, N, value);
	if (result < N)
		printf("%d is %d in array\n", value, result);
	else
		printf("%d is not in array\n", value);


	value = 12;
	result = binary_search(0, N, value);
	if (result < N)
		printf("%d is %d in array\n", value, result);
	else
		printf("%d is not in array\n", value);

	value = 100;
	result = binary_search(0, N, value);
	if (result < N)
		printf("%d is %d in array\n", value, result);
	else
		printf("%d is not in array\n", value);

	return 0;
}

 

Test Result #1

Test Result 는 36, 12, 100 을 찾는 Test Code 를 실행한 결과이다.

• 36 의 경우, S[ ] 의 index 8이 return 된다.
• 12 의 경우, S[ ] 의 index 5가 return 된다.
• 100 은 S[ ] 에 존재하지 않아 찾지 못한채로 0이 return 된다.

 

이 코드는 문제를 가지고 있다.

• 찾지 못한 경우의 index 가 0이 되고 실제 데이터 3이 들어있는 index 도 0이 되기 때문이다.

------------------ Test Data ------------------
[0] 3
[1] 8
[2] 9
[3] 11
[4] 12
[5] 22
[6] 23
[7] 31
[8] 36
[9] 45
-------------------- Test --------------------
36 is 8 in array
12 is 4 in array
100 is 0 in array

 

Update

찾지 못한 경우의 index 를 -1 로 return 하도록 처리하였다.

index_t binary_search(index_t low, index_t high, key_t x) {
	index_t mid;

	if (low > high)
        //! -1 을 반환하여 index 0 과 중복되지 않게 처리
		return -1; 
	else {
        //! 현재 low ~ high 의 중간 지점 찾기
		mid = (low + high) / 2;  

        //! 중간 지점이 key 값이면, index return;
		if (x == S[mid])      
			return mid;
		else if (x < S[mid]) //! 왼쪽 영역(중간보다 작은, low ~ mid-1)       
			return binary_search(low, mid - 1, x);
		else                 //! 오른쪽 영역(중간보다 큰, mid+1 ~ high)
			return binary_search(mid + 1, high, x);
	}
}

 

Test Result #2

• 존재하지 않는 경우 -1 이 return 된다.

------------------ Test Data ------------------
[0] 3
[1] 8
[2] 9
[3] 11
[4] 12
[5] 22
[6] 23
[7] 31
[8] 36
[9] 45
-------------------- Test --------------------
36 is 8 in array
12 is 4 in array
100 is -1 in array

 

이상입니다.

 

다음에는 이진 검색을 사용하여 해결할 수 있는 알고리즘 문제를 풀어보고 정리해보겠습니다.