<lower_bound, upper_bound> 정렬된 공간에서 이진 탐색

C++ 에서 이진탐색으로 원소를 탐색하는 함수가 제공된다는 것을 이번에 처음 알았다. 

<lower_bound> , <upper_bound> 가 있다. 

 

해당 함수를 사용할 때는 배열 혹은 벡터는 오름차순으로 정렬 되어야한다.

이진탐색은 그런 조건일 때 사용되는 알고리즘이기 때문이다. 

 

<lower_bound>

 - 이 함수를 쓰기 위한 용도로는 찾고자하는 값이 인덱스 몇번에 위치하는지 알고 싶을 때 사용하면 된다. 

이 함수의 반환형은 Iterator 이므로 첫 번째 주소를 가리키는 v.begin()을 빼줘야 한다. 이렇게 구현을 해준다면 인덱스 번호가 반환이 된다. 

 

<upper_boud> 

 - 찾으려는 값을 초과하는 숫자는 몇번째 인덱스에서 처음 등장하는지 알고 싶을 때 사용하면 된다. 

 

두개의 함수 모두 벡터나 배열의 시작 지점과 끝지점 그리고 찾고자하는 원소값을 인자로 둔다. 

아래의 코드를 보고 어떻게 사용하는지 익혀보자. 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {

	vector <int> v = { 1,2,3,4,5,6,7,8,9,10 };
	cout << endl;
	cout << "숫자 5의 인덱스 번호  : " << lower_bound(v.begin(), v.end(), 5) - v.begin() << endl;
	cout << "숫자 5의 다음 숫자의 인덱스 번호  : " << upper_bound(v.begin(), v.end(), 5) - v.begin() << endl;
	cout << "2~5까지의 숫자개수 : " << upper_bound(v.begin(), v.end(), 5) - lower_bound(v.begin(), v.end(), 2); 

}