[C++] binary_search, 이진 탐색

E woo·2023년 7월 10일

알고리즘

개발 일기

목록 보기

14/15

이진 탐색

이진 탐색은 정렬된 리스트에서 원하는 값을 찾고자 할 때 사용하며
Left , Right, Mid 를 통해 탐색할 때마다 검사 범위를 절반으로 줄여

O( $logN$ ) 을 갖는 탐색 방법이다.

단, 정렬된 리스트에서만 사용해야 하므로 vector 를 사용할 경우 sort 가 필요하며
set 에 경우는 저장될 때 정렬이 되므로 set 으로는 바로 사용 가능하다.

코드

binary_search()

vector 사용 (sort 필요)

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

using namespace std;

int main()
{

    int N;
    vector<int> my_v;

    my_v.push_back(2);
    my_v.push_back(5);
    my_v.push_back(1);
    my_v.push_back(4);
    my_v.push_back(6);
    my_v.push_back(7);

    cin >> N;

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

    if (binary_search(my_v.begin(), my_v.end(), N))
        cout << "찾음";
    else
        cout << "찾지 못함";

    return 0;
}

set 사용

#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

int main()
{

    int N;
    set<int> my_s;

    my_s.insert(2);
    my_s.insert(5);
    my_s.insert(1);
    my_s.insert(4);
    my_s.insert(6);
    my_s.insert(7);

    cin >> N;

    if (binary_search(my_s.begin(), my_s.end(), N))
        cout << "찾음";
    else
        cout << "찾지 못함";

    return 0;
}

algorithm 라이브러리의 binary_search 함수를 통해 원하는 원소가 정렬된 리스트에
있는지 없는지를 True, False 로 확인 할 수 있다.

만약 찾는 원소의 인덱스를 찾고 싶을 경우 lower_bound 와 upper_bound 를 사용한다.

lower_bound, upper_bound

lower_bound 는 탐색하고자 하는 값보다 크거나 같은 숫자가 처음 등장하는 위치를 찾고
upper_bound 는 탐색하고자 하는 값을 초과하는 숫자가 처음 등장하는 위치를 찾는다.

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

using namespace std;

int main()
{

    int N;
    vector<int> my_v;

    my_v.push_back(2);
    my_v.push_back(5);
    my_v.push_back(1);
    my_v.push_back(4);
    my_v.push_back(6);
    my_v.push_back(7);

    cin >> N;

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

    for (int i = 0; i < my_v.size(); i++)
        cout << my_v[i] << " ";

    cout << "\n";

    auto a = lower_bound(my_v.begin(), my_v.end(), N) - my_v.begin();
    auto b = upper_bound(my_v.begin(), my_v.end(), N) - my_v.begin();

    cout << a << " " << b;

    return 0;
}