Binary Search in C++ STL

* STL 내부의 이진탐색 관련 메서드 사용법에 관해 정리한 글 입니다.

→About Binary Search

---

#1binary_search method

#include <algorithm>
bool binary_search(first, last, value);

 

parameter Info

first : 탐색 시작 위치 (시작 이터레이터) * 배열의 경우 시작 주소

 last : 탐색 종료 위치 (종료 이터레이터) * 배열의 경우 마지막 주소

value : 탐색 타깃 데이터

 

▶ first ~ last 범위 내부에 타깃 데이터 (value) 가 존재하는지 O(LogN) 시간 복잡도로 탐색한다. 

▶ 만약 타깃 데이터가 존재한다면 true를 반환하고, 타깃 데이터가 존재하지 않는다면 false를 반환한다.

▶ 단, 원소가 정렬된 상태에서만 탐색이 가능하며, 정렬되지 않은 상태에서 탐색을 수행하는 경우 타깃 데이터를 탐색하지 못할 수 있다.

 

벡터 내부의 원소가 정렬되지 않은 상태에서 탐색을 수행한 예제

#include <iostream>
#innclude <algorithm>
#include <vector>
using namespace std;

int main() {

    vector<int> myVec = {1, 2, 9, 4, 5, 6, 7, 8, 9}; // 정렬 x

    // myVec 내부에 target이 존재하는지 binary_search 알고리즘을 사용해 탐색
    if (binary_search(myVec.begin(), myVec.end(), 5)) {
        cout << "myVec 내부에 target(5)가 존재합니다." << '\n';
    }
    else {
        cout << "myVec 내부에 target(5)가 존재하지 않습니다." << '\n';
    }
}

myVec 내부에 target(5)가 존재하지 않습니다.

 

벡터 내부의 원소가 정렬된 상태에서 탐색을 수행한 예제

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {

    vector<int> myVec = {1, 2, 9, 4, 5, 6, 7, 8, 9};
    sort(myVec.begin(), myVec.end()); // sort 함수를 사용해 벡터 내부의 원소를 정렬

    // myVec 내부에 target이 존재하는지 binary_search 알고리즘을 사용해 탐색
    // target이 존재한다면 true를 반환하고 존재하지 않는다면 false를 반환한다.
    if (binary_search(myVec.begin(), myVec.end(), 5)) {
        cout << "myVec 내부에 target(5)가 존재합니다." << '\n';
    }
    else {
        cout << "myVec 내부에 target(5)가 존재하지 않습니다." << '\n';
    }

}

myVec 내부에 target(5)가 존재합니다.

---

#2 lower_bound & upper_bound method

#include <algorithm>
std::lower_bound(first, last, value);
std::upper_bound(first, last, value);

 

parameter Info

first : 탐색 시작 위치

last : 탐색 종료 위치

value : 탐색 타깃 데이터 

 

lower_bound : 탐색 데이터 (value) 이상의 값 중 가장 작은 값이 나타나는 이터레이터를 반환한다. 

upper_bound : 탐색 데이터 (value) 보다 큰 값이 가장 처음으로 등장하는 위치의 이터레이터를 반환한다.

 

▶ 내부 동작 구조가 binary_search 알고리즘을 사용해 구현되어 있기에 O(LogN) 만큼의 시간복잡도가 소요된다.

▶  배열이 반드시 정렬된 상태에서 사용해야 정상적으로 동작한다.

 

#include <iostream>
#include <vector>
using namespace std;

int main() {

    vector<int> myVec = {1, 2, 3, 4, 4, 4, 7, 7, 9, 10};

    // upper_bound : targetData (4) 보다 큰 값이 가장 처음으로 나타나는 값을 가리키는 이터레이터를 반환한다. (7)
    vector<int>::iterator upper_it = upper_bound(myVec.begin(), myVec.end(), 4);
    // lower_bound : targetData (4) 이상의 값 중 가장 작은 값을 가리키는 이터레이터를 반환한다. (4)
    vector<int>::iterator lower_it = lower_bound(myVec.begin(), myVec.end(), 4);

    cout << "upper_bound(4) " << *upper_it << endl; // 7
    cout << "lower_bound(4) " << *lower_it << endl; // 4

}

upper_bound(4) 7
lower_bound(4) 4

 

 

#배열 내부에서 특정 원소의 개수를 탐색

▶ lower_bound, upper_bound 메서드를 활용해 선형 자료구조 (배열, 벡터 ..) 내부에서 특정 원소의 개수를 O(LogN)만에 탐색할 수 있다. 

▶upper_bound(4) (4 보다 큰 값이 등장하는 위치) 에서 lower_bound(4) (4가 처음으로 등장하는 위치) 의 값을 빼주면 원소 4의 개수가 출력된다.  

#include <iostream>
#include <vector>
using namespace std;

int main() {

    vector<int> myVec = {1, 2, 3, 4, 4, 4, 7, 7, 9, 10};

    cout << "원소 4의 개수 : " << upper_bound(myVec.begin(),myVec.end(), 4) - lower_bound(myVec.begin(), myVec.end(), 4) << endl;

}

원소 4의 개수 : 3