[C++] binary_search 정리

메모리 기반의 방대한 데이타가 있다고 가정을 할 때.. 이 데이터 목록 중 어떤 데이타가 존재하는지의 여부를 가장 빠르게 검색해주는 방식이 binary_search인데요. 이 STL 함수를 정리해 봅니다.

먼저 메모리 기반의 방대한 데이터를 준비해 봅니다.

#include <iostream>
#include <list>
#include <algorithm>
#include <iterator>

using namespace std;

int main()
{
    list<int> values{ 1, 2, 8, 7 ,6, 5, 4, 1, 9, 3, 5, 6, 7 };

}

데이타가 몇개 되지 않지만 방대하다고 칩시다. binary_search를 사용하기 위해서는 먼저 데이터가 정렬되어 있어야 합니다. 내림차순으로 정렬하는 코드를 추가하면.. 다음과 같습니다.

#include <iostream>
#include <list>
#include <algorithm>
#include <iterator>

using namespace std;

int main()
{
    list<int> values{ 1, 2, 8, 7 ,6, 5, 4, 1, 9, 3, 5, 6, 7 };
    auto predicate = [](int a, int b) { return a > b; };
    values.sort(predicate);

    copy(values.begin(), values.end(), ostream_iterator<double>{ std::cout, " "});
    cout << endl;
}

람다 함수로 내림차순 정렬을 위한 기준으로 삼았습니다. 그리고 잘 정렬되었는지 콘솔에 표시해 보았구요. 이제 binary_search 함수를 사용하기 위한 데이터 덩어리가 준비 되었고, 다음처럼 데이터 덩어리중 값 5가 존재하는지의 여부를 검색하는 코드는 다음과 같습니다.

#include <iostream>
#include <list>
#include <algorithm>
#include <iterator>

using namespace std;

int main()
{
    list<int> values{ 1, 2, 8, 7 ,6, 5, 4, 1, 9, 3, 5, 6, 7 };
    auto predicate = [](int a, int b) { return a > b; };
    values.sort(predicate);

    copy(values.begin(), values.end(), ostream_iterator<double>{ std::cout, " "});
    cout << endl;

    int wanted{ 5 };
    bool bSearched = binary_search(begin(values), end(values), wanted, predicate);
    if (bSearched) {
        cout << "Found !" << endl;
    } else {
        cout << "Not found." << endl;
    }
}