C++ 이진탐색 구현하기(재귀)

 

 

 

이진탐색이란?

 

 

 

정렬되어 있는 배열의 수를 효율으로 빠르게 찾는 방법입니다.

실생활에서 쓰일 수 있는 예로는...... 술게임의 업다운이 있습니다.

 

물론 해당 숫자를 찾을 때, 50, 25, 17.... 이런식으로 진행하면 안되지만..... 떠오르는 예제가 이것밖에 없내요..ㅎㅎ.....

 

 

 

 

시간 복잡도는 O(longN) 이며 

4,294,967,296개(약 43억개)를 32번만에 찾아낼 수 있는 빠른 알고리즘 입니다.

기초적이지만 재귀함수를 사용해 찾는 방법이라 재귀를 처음 접하거나 익숙하지 않다면 구현이 다소 어렵고 이해하기도 어렵습니다.

 

이런 좋은 알고리즘이지만 한가지 제약조건이 필요한데, 그것은 숫자가 정렬되어 있어야 한다는 점입니다.

 

 

 

우선 코드를 보겠습니다.

#include <iostream>

using namespace std;


template <typename T>
bool bin_search(int start, int end, const T * arr, const  T& n);

template <typename T>
class Binary_test {

public :
    bool search(const T * arr, int len, const T& n);
};


template <typename T>
bool Binary_test<T>::search(const T * arr, int len, const T& n) {
    int mid = len / 2;
    
    if (arr[mid] == n)
        return true;
    if (mid == 0)
        return false;

    if (arr[mid] < n)
        return bin_search(mid + 1, len - 1, arr, n);
    else
        return bin_search(0, mid - 1, arr, n);
}

template <typename T>
bool bin_search(int start, int end, const T * arr, const  T& n) {
    int mid = (start + end) / 2;
    if (arr[mid] == n)
        return true;
    
    if (start > end)
        return false;

    if(arr[mid] < n)
        return bin_search(mid + 1, end, arr, n);
    else
        return bin_search(start, mid - 1, arr, n);
}

int main(void) {

    Binary_test<int> b;
    int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
    int len = sizeof(arr) / sizeof(int);
    int input[13] = { 0,1,2,3,4,5,6,7,8,9,10,11,12 };
    
    for (int i = 0; i < 13; i++) {
        if (b.search(arr, len, input[i]))
            cout << input[i] << " 있습니다." << endl;
        else
            cout << input[i] << " 없습니다." << endl;
    }

    return 0;
}

 

실행결과

 

 

 

 

물론, 코드를 더 쉽고 간결하게 만들 수 있었지만.... 최대한 사용자 입장에서 쓰기 편하도록 설계해봤습니다.

 

숫자를 하나 선정한 후 계속 중간 값과 비교해서 경우의 수를 추려나가는 형식입니다.

 

27, 29행을 보면 mid값에 +1 or -1 을 해주고 있는데 이 뜻은 중간값을 비교했다는 점에서 

더이상 해당 값과 비교할 필요가 없어졌기 때문입니다.

 

그림으로 설명해 보자면 다음과 같습니다.

 

 

 

 

 

 

 

 

 

 

 

 

이번엔 다른수를 해보겠습니다.

 

 

 

 

 

 

 

 

여기서 알 수 있는 사실은 찾는 값이 없다면 start값은 end보다 커지게 됩니다. 

 

mid 값이 왼쪽으로 가도 마찬가지 입니다.

 

왜냐하면 왼쪽으로 가게된다면 end 값이 계속 mid 값으로 바뀌기 때문입니다.

 

따라서 38행을 보면 'if(start > end) return false;' 로 정의가 된 것입니다.

 

 

 

 

다시한번 말씀 드리지만 재귀함수는 처음에 이해하기 굉장히 어렵습니다. 때문에 익숙해 지기 위해선.....

 

데이터 값을 일일이 넣어보고 손수 한번한번씩 돌려보면서 이해하는 방법밖엔 없을 것 같습니다.

 

제가 이렇게 해서 이해를 했거든요......