이진 탐색 알고리즘의 재귀적 구현

이진 탐색의 알고리즘을 재귀적으로 구현해 보았다.

 

재귀적으로 구현해 성능은 좋지 않다.

 

이 알고리즘에서는 재귀적 성격을 다음의 반복적인 패턴에서 찾을수 있다.

 

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

 

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

 

그리고 탐색 대상을 찾을때 까지 위 2가지 패턴을 반복한다.

 

 

 

public class b_04_RecursiveBinarySearch 
{
    static int BSearchRecur(int ar[], int first, int last, int target) 
    {
    if(first > last)//재귀 탈출 조건
        return -1;// -1의 반환은 탐색의 실패를 의미
    
    int mid = (first+last) / 2;// 탐색대상의 중앙을 찾는다.
    
    if(ar[mid] == target)
        return mid;// 검색된 타겟의 인덱스 값 반환
    else if(target < ar[mid])
        return BSearchRecur(ar, first, mid-1, target);//자기자신을 다시 호출
    else
        return BSearchRecur(ar, mid+1, last, target);//자기자신을 다시 호출
    }
        public static void main(String[] args) 
        {
            int arr[] = {1, 3, 5, 7,9};
            int idx;
 
            idx = BSearchRecur(arr, 0, arr.length-1, 7);
            
            if(idx == -1)
                System.out.printf("탐색 실패 \n");
            else
                System.out.printf("타겟 저장 인덱스: %d \n", idx);
        }
}

 

타겟 저장 인덱스: 3