[C++] std::binary_search

이진 탐색

개요

출처: cppreference

 

　예전 이진 탐색에 대한 개념적인 부분을 해당 글에서 다룬 적이 있었다. 다시 상기하자면, 정렬된 배열을 반으로 나눠가며 원하는 값을 찾는 알고리즘이 이진 탐색이다. 이번 시간에는 해당 알고리즘을 구현한 std::binary_search 함수에 대한 사용법을 알아보도록 하자.

---

본문

사용법

　이진 탐색 또한 탐색의 일종이므로, 배열 내에서 특정 요소가 존재하는지 확인할 때 사용된다. 이때 대상 범위가 이미 정렬되어 있어야 하며, 중복 요소가 있는 경우 어느 요소인지 알 수 없다. 이는 함수가 단순히 주어진 값이 배열 내에 존재하는지 여부만을 체크하기 때문이다.

 

#include <iostream>
#include <algorithm>
#include <vector>

int main() 
{
    std::vector<int> v = { 1, 2, 4, 5, 9, 10 };

    if (std::binary_search(v.begin(), v.end(), 5)) 
        std::cout << "Value found!" << "\n";

    else 
        std::cout << "Value not found." << "\n";

    return 0;
}

　정렬된 동적 배열 v에서 5라는 값을 찾고 싶을 때 다음과 같이 std::binary_search(배열의 시작 위치, 배열의 끝 위치, 찾고자 하는 값)의 형식으로 해당 함수를 사용하면 된다.

 

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

int main() 
{
    unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
    std::default_random_engine generator(seed);
    std::uniform_int_distribution<int> distribution(0, 100);
    std::vector<int> v(10);

    for (int i = 0; i < 10; ++i)
    {
        v[i] = distribution(generator);
        std::cout << v[i] << ' ';
    }

    int num = 15;

    if (std::binary_search(v.begin(), v.end(), num))
        std::cout << "\n" << num << " found\n";

    else 
        std::cout << "\n" << num << " not found\n";

    return 0;
}

 

　이번엔 정렬되지 않은 배열을 생성해서 임의의 수를 찾게 설계해 보았다. 분명 배열 내에 15라는 원소가 있음에도 불구하고 존재하지 않는다는 결과를 반환한다. 이는 범위를 절반으로 줄이는 과정에서 중간 값과 찾고자 하는 값을 비교하며 탐색하기 때문이다. 

 

#include <iostream>
#include <algorithm>
#include <vector>

int main() 
{
    std::vector<int> v = { 15, 30, 13, 65, 98, 13, 70, 14, 88, 93 };
    int num = 15;

    std::sort(v.begin(), v.end());
    for (auto it = v.begin(); it != v.end(); ++it)
        std::cout << *it << ' ';

    if (std::binary_search(v.begin(), v.end(), num))
        std::cout << "\n" << num << " found\n";

    else 
        std::cout << "\n" << num << " not found\n";

    return 0;
}

 

　앞서 랜덤하게 생성한 배열을 정렬 후 탐색을 진행하니, 탐색 결과가 정확하게 나오는 것을 확인할 수 있다.

---

요약

std::binary_search()
1. 정의: 이진 탐색 알고리즘
2. 특징
　a. O(logN)의 탐색 속도, 하지만 추가적인 정렬이 필요할 경우 정렬 시간만큼 추가 소요 O(NlogN)
　b. 대상의 범위가 이미 정렬되어야 함
　c. 중복 요소 구분 불가