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

#include <iostream>
using namespace std;

int bsearch(int data[], int target, int start, int end)
{
    int mid = (start + end) / 2;
    if(start > end)
        return -1;
    if(data[mid] == target)
        return mid;
    else if(target > data[mid])
        return bsearch(data, target, mid+1, end);
    else if(target < data[mid])
        return bsearch(data, target, start, mid-1);
}

이진탐색 알고리즘의 논리는 재귀적이기 때문에, 충분히 재귀함수로 구현할 수 있다.

이진탐색 알고리즘의 논리는 아래와 같은 작업들이 반복된다.

1. 중앙 인덱스 값과 target 값을 비교
2. target 값이 더 크다면, start 값을 mid 오른쪽으로, 아니라면 end값을 mid 왼쪽으로 옮긴다.

이진탐색은 start값과 end 값이 겹쳐질때까지 비교해야 함으로, 재귀함수에서는 start값이 end값보다 커지면 탈출시키도록 한다.