이진 검색(Binary Search)

코딩 테스트를 위한 자료 구조와 알고리즘 with C++

 

 

이진 검색

• 분할 정복 알고리즘의 하나이다.
• 시퀀스(정렬된 상태)에서 검색 범위를 2배씩 줄여나가며 검색한다.
• O(log n) 복잡도를 갖는다.
• 재귀를 이용하면 쉽게 구현할 수 있다.

 

이진 검색 과정

1. 시작 F, 끝 L의 전체 시퀀스를 범위로 잡는다.
2. 가운데 원소 M을 정한다.
3. M이 찾는 원소이면 끝낸다.
4. F와 L이 같은 경우 찾지 못 한 상태로 끝낸다.
5. 찾는 원소가 M보다 작으면 끝 L을 M - 1로 설정하고, M보다 크면 시작 F를 M + 1로 설정한다.
6. 2부터 다시 반복한다.

 

선형 검색과 이진 검색의 성능 비교

 

#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <algorithm>

using namespace std;

bool linear_search(int N, vector<int>& S)
{
    for (int e : S)
        if (e == N)
            return true;

    return false;
}

bool binary_search(int N, vector<int>& S)
{
    auto first = S.begin();
    auto last = S.end();

    while (true)
    {
        int range_length = distance(first, last);
        auto mid_element_pos = first + range_length / 2;
        int mid_element = *mid_element_pos;

        if (mid_element == N)
            return true;
        else if (mid_element > N)
            last = mid_element_pos - 1;
        else
            first = mid_element_pos + 1;

        if (range_length < 1)
            return false;
    }
}

bool binary_search_recursive(int N, vector<int>& S, vector<int>::iterator first, vector<int>::iterator last)
{
    int range_length = distance(first, last);
    auto mid_element_pos = first + range_length / 2;
    int mid_element = *mid_element_pos;

    if (mid_element == N)
        return true;

    if (range_length < 1)
        return false;

    if (mid_element > N)
        return binary_search_recursive(N, S, first, mid_element_pos - 1);
    else
        return binary_search_recursive(N, S, mid_element_pos + 1, last);
}

void run_small_search_test()
{
    int N = 2;
    vector<int> S{1, 3, 2, 4, 5, 7, 9, 8, 6};

    sort(S.begin(), S.end());

    if (linear_search(N, S))
        cout << "선형 검색으로 원소를 찾았습니다!" << endl;
    else
        cout << "선형 검색으로 원소를 찾지 못했습니다." << endl;

    if (binary_search(N, S))
        cout << "이진 검색으로 원소를 찾았습니다!" << endl;
    else
        cout << "이진 검색으로 원소를 찾지 못했습니다." << endl;
}

void run_large_search_test(int size, int N)
{
    vector<int> S;
    random_device rd;
    mt19937 rand(rd());

    // [1, size] 범위에서 정수 난수 발생
    uniform_int_distribution<mt19937::result_type> uniform_dist(1, size);

    // S에 난수 추가
    for (int i = 0; i < size; ++i)
        S.push_back(uniform_dist(rand));

    sort(S.begin(), S.end());

    // 검색 시간 측정 시작
    chrono::steady_clock::time_point begin = chrono::steady_clock::now();

    bool search_result = binary_search_recursive(N, S, S.begin(), S.end());

    // 검색 시간 측정 종료
    chrono::steady_clock::time_point end = chrono::steady_clock::now();

    auto diff = chrono::duration_cast<chrono::microseconds>(end - begin);
    cout << "이진 검색 수행 시간: " << diff.count() << endl;

    if (search_result)
        cout << "원소를 찾았습니다." << endl;
    else
        cout << "원소를 찾지 못했습니다." << endl;
}

void main()
{
    run_small_search_test();

    run_large_search_test(100000, 36543);
    run_large_search_test(1000000, 36543);
    run_large_search_test(10000000, 36543);
}

 

시퀀스의 크기가 커질수록 선형과 이진 검색의 수행 시간 차이가 커졌다.

 

 

또한, Debug에서 Release 모드로 바꾸자 눈에 띄게 성능이 향상되었다.