더북(TheBook)

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;
}

신간 소식 구독하기
뉴스레터에 가입하시고 이메일로 신간 소식을 받아 보세요.