[자료구조] 이진 탐색 알고리즘의 재귀적 구현

◆이진 탐색 알고리즘의 반복 패턴을 정리해보면

1, 탐색 범위의 중앙에 목표 값이 저장되었는지 확인

2. 저장되지 않았다면 탐색 범위를 밤으로 줄여서 다시 탐색 시작

​

◆이진 탐색 알고리즘의 탐색 실패가 결정되는 시점

:탐색 범위의 시작위치를 의미하는 first가 탐색 범위의 끝을 의미하는 last보다 커지는 경우

→재귀 함수의 탈출 조건이 된다!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

 

#include <stdio.h>

int BSearchRecur(int ar[], int first, int last, int target) {
	int mid;
	if(first > last)
		return -1; // -1의 반환은 탐색의 실패.

	mid = (first + last) / 2; // 탐색 대상의 중앙을 찾음
	if(ar[mid] == target)
		return mid; // 탐색된 대상의 인덱스 값 반환
	else if(ar[mid] > target)
		return BSearchRecur(ar, first, mid-1, target);
	else
		return BSearchRecur(ar, mid+1, last, target); 	
}

int main(void) {
	int idx;
	int arr[] = {1, 3, 5, 7, 9};

	idx = BSearchRecur(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1, 7);
	if(idx == -1)
		printf("탐색실패\n");
	else
		printf("타겟 저장 인덱스 : %d\n", idx);

	idx = BSearchRecur(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1, 4);
	if(idx == -1)
		printf("탐색실패\n");
	else
		printf("타겟 저장 인덱스 : %d\n", idx);

}

​

◆실행결과

타겟 저장 인덱스: 3

탐색 실패

​

 

---

기존의 이진 탐색 알고리즘 구현 코드에서 while문을 재귀함수를 사용함으로써 없앨 수 있고

else문안에 있는 if else 문을 없앨 수 있다 !!