[C++/STL] binary search (이분 탐색)

2018. 3. 8 에 쓰여진 글 입니다.

---

1. 이분탐색은 정렬 되어있는 경우에 한에서만 가능하다. (오름차순정렬일때만!)

2. 탐색효율이 좋고 탐색 시간이 적게 소요된다.

시간복잡도

3. stl 이용할 경우 binary_search(v.begin(), v.end(), 찾을값) 을 하면 true 또는 false를 반환한다.

 

#include <iostream>
#include <vector>        //vector위한 헤더
#include <algorithm>    //binary search 위한 헤더
 
using namespace std;
 
vector < int > v;
 
int main()
{
    v.push_back(1);                //1넣기
    v.push_back(5);                //5넣기
    v.push_back(3);                //3넣기
    sort(v.begin(), v.end());    //벡터 정렬
    for (int i = 1; i <= 5; i++) {
        if (binary_search(v.begin(), v.end(), i))
            cout << i << "는 벡터 안에 존재합니다" << endl;
        else
            cout << i << "를 찾을수 없어요 ㅠㅠ" << endl;
    }
 
    return 0;
}

 

만약 정렬을 안했다면??

#include <iostream>
#include <vector>        //vector위한 헤더
#include <algorithm>    //binary search 위한 헤더
 
using namespace std;
 
vector < int > v;
 
int main()
{
    v.push_back(1);                //1넣기
    v.push_back(5);                //5넣기
    v.push_back(3);                //3넣기
    //sort(v.begin(), v.end());    //벡터 정렬
    for (int i = 1; i <= 5; i++) {
        if (binary_search(v.begin(), v.end(), i))
            cout << i << "는 벡터 안에 존재합니다" << endl;
        else
            cout << i << "를 찾을수 없어요 ㅠㅠ" << endl;
    }
 
    return 0;
}

 

관련문제

https://blog.naver.com/kms32123/221224431625

[백준/BOJ] 1920번 수 찾기 풀이 (C++)