[ C++ ] 이진 탐색 함수 lower_bound, upper_bound

lower_bound

- 이진탐색(Binary Search)기반의 탐색 방법이다. (배열 또는 리스트가 정렬 되어있어야 한다.)
- lower_bound는 찾으려 하는 key값이 "없으면" key값보다 큰 가장 작은 정수 값을 찾는다.
- 같은 원소가 여러개 있어도 상관 없으며, 항상 유일한 해를 구할 수 있습니다.

- <algorithm> 헤더 파일에 있음

 

STL의 lower_bound 함수

template <class ForwardIterator, class T>
	ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val);

반환형이 Iterator 이므로 vector container인 경우에는 iterator에서 v.begin()을 뺀 값으로 몇 번째 인자인지 계산을 하고,
배열인 경우에는 배열의 첫번째 주소를 가리키는 배열의 이름을 빼면 몇 번째 인자인지 알 수 있습니다. 

 

사용 예시를 보자.

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
 
int main() {
    vector<int> v = {1,2,4,5,6,7};
    vector<int>::iterator it = lower_bound(v.begin(), v.end(), 3);
    cout<<it-v.begin()<<" "<<*it;  //결과 : 2 4
}

반환형이 iterator인 것을 이용하여 인덱스와 값을 알아낼 수 있다.

 

 

 

---

upper_bound

- lower_bound와 마찬가지로 이진탐색(Binary Search)기반의 탐색법 입니다.
- 이진탐색(Binary Search)기반이므로 배열이나 리스트가 오름차순으로 정렬 되어있어야 합니다.
- upper_bound는 key값을 초과하는 가장 첫 번째 원소의 위치를 구하는 것 입니다.
- 같은 원소가 여러개 존재 해도 항상 유일한 해를 구할 수 있습니다.

 

STL upper_bound

template <class ForwardIterator, class T>
	ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val);

lower_bound함수와 비슷하다.

 

사용 예시

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
 
 int main() {
    vector<int> v = {1,2,4,5,6,7};
    vector<int>::iterator it = upper_bound(v.begin(), v.end(), 4);
    cout<<it-v.begin()<<" "<<*it;  //결과 : 3 5
}