[Algorithm] Binary Search 의 간단한 구현 (C++)

Linear Search 보다는 상대적으로 복잡하지만 

자료구조의 원소가 "정렬"되어 있을 경우 O(log n)으로 동작하는 이진 탐색을 반복문과 재귀함수로 구현해보도록 하겠습니다.

 

먼저 이진탐색의 로직은 정렬되어 있는 데이터의 첫번째 부분 first, 데이터의 마지막 원소 last 인덱스를 구한뒤 

(first + last) / 2를 통해 mid인덱스를 구합니다. (나머지는 버립니다)

이후 mid인덱스에 들어 있는 값이 찾을려고 하는 값과 같다면 그대로 값을 찾은 것이고

찾을려고 하는 값이 mid인덱스에 들어있는 값보다 작다면 last를 mid - 1로 변경한뒤 

first와 last를 다시 합한뒤 2로 나누어 mid를 다시 구해 줄 수 있습니다.

 

종료 조건은 first가 last보다 클 경우 입니다.

first와 last가 같은 경우는 종료 조건이 아니라 탐색의 대상이 아직 하나 남아 있는 상태입니다!

 

실제로 1, 5, 9, 12가 데이터로 있을 경우 찾을려고 하는 값이 12일 경우

first = 0(1), last = 3(12)로 잡으면 mid는 1(5)가 됩니다.

현재 target값이 9이니까 mid보다 큽니다. 따라서 first를 mid + 1로 변경해줍니다.

 

그리고 다시한번 first = 2(9), last = 3(12) 가 됩니다. mid는 2(9)로 잡아줍니다.

여전히 target값이 mid보다 크기 때문에 first값을 mid + 1로 변경해줍니다. 그렇게 되면 first의 값은 3(12)가 됩니다.

 

이렇게되면 first의값과 last의 값 (인덱스 값)이 같은데 여기서 종료하는게 아니라 first가 가르키는 값이 target과 같은지 비교하는 작업이 한번 남아 있기 때문에 

종료 조건은 first가 last 보다 큰 경우 입니다.

 

이를 반복문으로 구현을 하면 

#include <bits/stdc++.h>
using namespace std;

#define endl "\n"

int BS(int a[], int len, int t)
{   
    int f = 0;
    int l = len - 1;
    int m;

    while (f <= l)
    {
        m = (f + l) / 2;
        if (t == a[m]) return m;
        else 
        {
            if (t < a[m]) l = m - 1;
            else f = m + 1;
        }
    }
    return -1;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int a[] = {1, 3, 5, 7, 9};
    int idx;
    idx = BS(a, sizeof(a) / sizeof(int), 9);
    if (idx == -1) cout << "F!" << endl;
    else cout << a[idx] << endl;
    
    return 0;
}

위와 같이 구현할 수 있습니다.

 

이를 재귀적으로 구현을 하면

#include <bits/stdc++.h>
using namespace std;

#define endl "\n"

int BS(int a[], int f, int l, int t)
{
    if (f > l) return -1;

    int m = (f + l) / 2;

    if (t == a[m]) return m;
    else if (t < a[m]) return BS(a, f, m - 1, t);
    else  return BS(a, m + 1, l, t);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int a[] = {1, 3, 5, 7, 9};
    int idx;
    idx = BS(a, 0, sizeof(a) / sizeof(int) - 1, 7);
    if (idx == -1) cout << "F!" << endl;
    else cout << "idx : " << idx << " value : " << a[idx] << endl;
    
    return 0;
}