[C언어] 재귀 함수 - 이진 탐색 (Binary Search)

※요약

C언어에서 재귀 호출을 이용한 이진 탐색이다. 이진 탐색이란 이름 그대로 탐색할 데이터를 반으로 나눠 나머지 반만 탐색하는 방식을 반복하는 알고리즘이며 빠른 속도로 원하는 값을 찾을 수 있다. 이진 검색, 이분 검색 등으로도 불린다.

※특징

 - 각 요소의 값들은 정렬되어 있어야 한다.

 - 각 요소의 값들은 모두 달라야 한다.

※예제

#include <stdio.h>

int RecusiveBinSearch( int nArr[], int nBegin, int nEnd, int nTarget )
{
	int nMid = 0;

	if( nBegin > nEnd )
	{
		return -1;	//탈출 조건 및 탐색 실패
	}

	nMid = (nBegin+nEnd) / 2;

	if( nArr[nMid] == nTarget )
	{
		return nMid;			//타겟을 찾았다.
	}
	else if( nTarget < nArr[nMid] )
	{
		return RecusiveBinSearch( nArr, nBegin, nMid-1, nTarget );
	}
	else
	{
		return RecusiveBinSearch( nArr, nMid+1, nEnd, nTarget );
	}
}

int main( )
{
	int nArr[] = { 1, 3, 5, 7, 9, 11, 13 };
	int nResult;

	nResult = RecusiveBinSearch( nArr, 0, sizeof(nArr)/sizeof(int)-1, 7 );
	
	if(nResult == -1)
	{
		printf( "값이 없습니다.\n" );
	}
	else
	{
		for( int i=0 ; i<sizeof(nArr)/sizeof(int) ; ++i )
		{
			printf( "%d ", nArr[i] );
		}
		printf( "\n%d번째 배열 요소에 있습니다.\n", nResult );
	}

	return 0;
}

※결과