JArchive 프로그래밍 일기

이진 탐색 알고리즘을 재귀 함수를 이용하여 다시 구현해본다. 

first : 탐색 범위의 시작을 나타냄

last : 탐색 범위의 끝을 나타냄 

mid : 탐색 범위의 중간값을 나타냄 

<이진 탐색 알고리즘의 순서>

1. 중간(mid)값이 target이면 반환한다. 

2. target이 아닌 경우, 검색 대상을 반으로 줄인다. (first 또는 last를 갱신)

3. 1과 2를 반복한다. 

<재귀함수의 탈출조건 2가지>

1. first가 last보다 커지는 경우 재귀함수를 탈출한다. 

2. target을 찾았다면 재귀함수를 탈출한다. 

전체 코드 

#include <stdio.h>

int BSRecursive(int *ar, int first, int last, int target)
{
	int mid;
	if (first > last)
		return -1;		//탐색 실패 

	mid = (first + last) / 2;

	if (target == ar[mid])
		return mid;			//탐색 성공. index 반환.
	else if (ar[mid] > target)
		return BSRecursive(ar, first, mid - 1, target);
	else
		return BSRecursive(ar, mid + 1, last, target);
}

int main()
{
	int ar[] = { 1, 3, 5, 7, 9 };	//이진 검색의 전제는 '정렬된'배열이다.
	int index; 
	int first = 0, last = sizeof(ar) / sizeof(int)-1;

	index = BSRecursive(ar, first, last, 2);	//target = 2인 경우
	if (index == -1)
		printf("탐색 실패!\n");
	else
		printf("index of target : %d\n", index);
	
	index = BSRecursive(ar, first, last, 7);	//target = 7인 경우 
	if (index == -1)
		printf("탐색 실패!\n");
	else
		printf("index of 7 : %d\n", index);

	return 0;
}