[C++] lower_bound와 upper_bound 함수

<lower_bound와 upper_bound 함수>

 

c++에서는 이진 탐색으로 원소를 탐색하는 lower_bound, upper_bound 함수를 제공

 

용도: 찾으려는 key 값보다 같거나 큰 숫자가 배열의 몇 번째 index에서 처음 발견되는지 찾기 위함임

(반드시 오름차순 정렬 되어 있어야 함)

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

int main() {

	int arr[6] = { 1,2,3,4,5,6 };
	cout << "lower_bound(6) : " << lower_bound(arr, arr + 6, 6) - arr; // lower_bound(6) : 5

	return 0;
}

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

int main() {

	vector<int> arr = { 1,2,3,4,5,6 };
	cout << "upper_bound(3) : " << upper_bound(arr.begin(), arr.end(), 3) - arr.begin();
	// upper_bound(3) : 3
    
	return 0;
}

 

 

이럴때 사용하자!!

 

1. 특정 범위에 속하는 숫자들이 몇 개 있는지 탐색할 때

2. 특정한 숫자가 몇 번 나오는지 탐색할 때