[ 알고리즘 ] 이진 탐색 알고리즘의 재귀적 구현(C언어)

 

</div

C언어로 이진 탐색 알고리즘의 재귀적 구현하기

 

 

이진 탐색 알고리즘을 재귀함수 기반으로 구현하겠습니다. 

다음과 같은 반복 패턴이 있기 때문에 충분히 가능합니다.

 

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

2. 아니라면 탐색 범위를 반으로 줄여서 다시 탐색 시작 

 

이진 탐색 알고리즘

 

 

탐색 범위의 시작 위치를 나타내는 first가 탐색 범위의 끝을 나타내는 last보다 커지는 경우, 탐색을 끝냅니다.

즉, 재귀적으로 표현했을 때 '탈출 조건'이 될 수 있습니다. 재귀함수의 탈출 조건은 탐색 대상을 찾았거나 탐색 대상이 배열이 존재하지 않는 경우에 이뤄지기 때문입니다. 

 

이진 탐색 알고리즘 코드(재귀 적용 하지 않음)

 

 

---

그럼 재귀함수 기반으로 재구현한 이진 탐색 알고리즘 코드를 보겠습니다. 

 

#include <stdio.h>

int BinarySearchRecur(int array[], int first, int last, int target){
    int mid;
    if(first > last) // 탈출 조건
        return -1;  // -1 반환은 탐색의 실패 의미
    mid = (first+last)/2;
    
    if(array[mid] == target)
        return mid; // 탐색된 타켓의 인덱스 값 반환
    else if (array[mid] > target)
        return BinarySearchRecur(array, first, mid-1, target);
    else
        return BinarySearchRecur(array, mid-1, last, target);
    
}

int main(void) {
    int arr[]={1, 3, 4, 7, 8};
    int index;
    
    index = BinarySearchRecur(arr, 0, sizeof(arr)/sizeof(int)-1, 3);
    
    if(index == -1)
        return printf("탐색 실패 \n");
    else
        return printf("타켓 저장 인덱스: %d \n",index);

}

 

 

 

------------------------------

알고리즘 개념 모아보기 

------------------------------