[C++] lower_bound(), upper_bound() ; 이진 탐색(Binary Search)

lower_bound(), upper_bound() ; 이진 탐색(Binary Search)

 

소개

• 이진 탐색(Binary Search)으로 원소를 탐색하는 함수
  • 시간 복잡도가 $O(\log_{2} N)$ 으로, 빠른 속도로 탐색을 수행할 수 있다.
• 탐색을 진행할 컨테이너는 반드시 오름차순으로 정렬되어 있어야 한다.

 

필요한 헤더

#include <algorithm>

 

형식

• 찾은 값(val)의 주소를 Iterator 형으로 반환한다.

lower_bound(ForwardIterator first, ForwardIterator last, const T& val)

lower_bound(ForwardIterator first, ForwardIterator last, const T& val)

 

lower_bound()

• 찾으려는 키 값보다 크거나 같은(이상, ≥) 숫자가 컨테이너에서 처음 등장하는 주소를 Iterator 형으로 반환한다.

 

사용 예

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

vector<int> V = { 1, 2, 3, 4, 5, 6, 7, 8 ,9 };

int main() {
    cout << "lower_bound(6) : " << lower_bound(V.begin(), V.end(), 6) - V.begin() << endl;

    return 0;
}

lower_bound(6) : 5

• 벡터 V에서 6 이상의 숫자가 처음으로 나오는 위치(6)의 인덱스 번호는 5이다.
• lower_bound() 함수의 반환형은 Iterator로, 실제로 몇 번째 인덱스인지 확인하려면 lower_bound() 값에서 벡터의 첫 번째 주소의 위치값(V.begin())을 빼주면 된다.
  • 그렇지 않을 경우 컴파일 에러가 발생한다.

 

upper_bound()

• 찾으려는 키 값을 초과(>)하는 숫자가 컨테이너에서 처음 등장하는 주소를 Iterator 형으로 반환한다.

 

사용 예

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

vector<int> V = { 1, 2, 3, 4, 5, 6, 7, 8 ,9 };

int main() {
    cout << "upper_bound(7) : " << upper_bound(V.begin(), V.end(), 7) - V.begin() << endl;

    return 0;
}

upper_bound(7) : 7

• 벡터 V에서 7을 초과하는 숫자(8)가 처음으로 나오는 위치의 인덱스 번호는 7이다. 
• upper_bound() 함수의 반환형은 Iterator로, 실제로 몇 번째 인덱스인지 확인하려면 upper_bound() 값에서 벡터의 첫 번째 주소의 위치값(V.begin())을 빼주면 된다.
  • 그렇지 않을 경우 컴파일 에러가 발생한다.

 

활용 방법

오름차순으로 정렬된 자료에서 특정 범위에 속하는 숫자들이 몇 개 있는지 탐색하고자 할 때

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

vector<int> V = { 1, 2, 2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 5, 6, 7, 8, 9, 10 };

int main() {
    cout << "2이상 4 이하의 원소 개수 : " << upper_bound(V.begin(), V.end(), 4) - lower_bound(V.begin(), V.end(), 2) << endl; 
  
    return 0;
}

2이상 4 이하의 원소 개수 : 9

• upper_bound() 값은 4를 초과하는 수(5)가 처음 등장하는 위치(인덱스 10)의 주소값을 반환하고, lower_bound() 값은 2 이상의 수(2)가 처음 등장하는 위치(인덱스 1)의 주소값을 반환한다. 

 

오름차순으로 정렬된 자료에서 특정한 숫자가 몇 번 나오는지 탐색하고자 할 때

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

vector<int> V = { 1, 2, 2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 5, 6, 7, 8, 9, 10 };

int main() {
    cout << "4의 개수 : " << upper_bound(V.begin(), V.end(), 4) - lower_bound(V.begin(), V.end(), 4) << endl; 
  
    return 0;
}

4의 개수 : 4

• upper_bound() 값은 4를 초과하는 수(5)가 처음 등장하는 위치(인덱스 10)의 주소값을 반환하고, lower_bound() 값은 4 이상의 수(2)가 처음 등장하는 위치(인덱스 6)의 주소값을 반환한다.