1.6.7 재귀적 이진 검색
문제 1-20 오름차순 정수 배열에서 재귀적 방법으로 특정 값이 배열에 존재하는지 찾으세요.
해결책 앞에서 유사한 반복 해결책을 살펴보았습니다. 이번에는 같은 문제를 재귀 해결책으로 살펴봅니다. 재귀 해결책에서는 검색 공간을 절반으로 나누고 나머지는 버립니다. 각 단계에서 검색 공간의 절반을 버리므로 매우 효율적입니다.
해결책 1-20 오름차순 정수 배열에서 값 찾기
int BinarySearchRecursive(int arr[], int low, int high, int value) { if (low > high) { return -1; } int mid = (low + high) / 2; if (arr[mid] == value) { return mid; } else if (arr[mid] < value) { return BinarySearchRecursive(arr, mid + 1, high, value); } else { return BinarySearchRecursive(arr, low, mid - 1, value); } } /* 테스트 코드 */ int main() { int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; printf(" %d ", BinarySearchRecursive(arr,0,sizeof(arr) / sizeof(int) - 1, 6)); printf(" %d ", BinarySearchRecursive(arr,0,sizeof(arr) / sizeof(int) - 1, 16)); return 0; }