lower_bound, upper_bound

lower_bound()

key <= n인 n이 배열에서 언제 처음 등장하는지 인덱스를 찾음.
조건: 배열이나 벡터가 오름차순 정렬되어있어야 함.

//인덱스 출력, arr을 빼지 않으면 주소 출력
lower_bound(arr,arr+6,target)-arr;
벡터 : lower_bound(arr.begin(),arr.end(),target)-arr.begin();

upper_bound

key 값을 초과하는 숫자가 배열 몇 번째에서 처음 등장하는지 찾음
조건: 배열 또는 벡터가 오름차순 정렬되어 있어야 함.

활용 대상 문제

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

ex) 5이상 11이하의 숫자가 몇 개인지 구할 때

vector<int> arr = { 1,3,5,5,7,8,8,10,10,11,13 };
	cout << "5 이상 11 이하의 갯수 : " << upper_bound(arr.begin(), arr.end(), 10) - lower_bound(arr.begin(), arr.end(), 4);

2. 오름차순 정렬된 자료에서 특정한 숫자가 몇 번 나오는지 탐색할 때 -> O(logN)으로 탐색 가능

vector<int> arr = { 1,3,5,5,5,8,8,10,10,11,13 };
	cout << "count of 5 : " << upper_bound(arr.begin(), arr.end(), 5) -
		lower_bound(arr.begin(), arr.end(), 5);