lower_bound

: 타겟값의 이상이 되는 첫번째 위치를 반환함.

• 선행 조건으로는 오름차순으로 정렬되어 있어야 한다.

-> 시작 복잡도는 log(n)이다.!

관련 문제

• 백준 : 11053 가장 긴 증가하는 부분 수열

• low_bound 에서 end 값을 조절하면서 접근하는 문제임.
  : 어려움..

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <string>

int n, lis[1001], len, num;
int main() {
	scanf("%d", &n);

	vector<int>v(n, 0);

	for (int i = 0; i < n; i++) {
		scanf("%d", &num);
		//auto lowerPos = lower_bound(lis, lis + len, num);

		// end 값 범위가 중요함 
		// 
		auto lowerPos = lower_bound(v.begin(), v.begin() + len, num);

		// 이 조건으로 하면 안됨. 
		// 왜냐 하면 low_bound 범위 설정을 다르게 했기 때문
		//if (lowerPos == v.end())
		//	len++;

		// 
		if (*lowerPos == 0)
			len++;
		*lowerPos = num;
		for (int j = 0; j < n; j++) {
			//printf("%d ", lis[j]);
			printf("%d ", v[j]);
		}
		printf("\n");
	}
	printf("%d", len);

	return 0;
}

=> 10 20 4 로 할 경우.
value 4보다 큰 10 20 에서 10을 찾게 되므로
10 20 -> 4 20 으로 갱신됨.

어디에 사용할까?

: 시간복잡도가 큰 문제에서 , 정렬된 경우, 타겟값보다 작은 값이
몇개 있는지 알고 싶을 때

• 관련 문제 : 7795번.

예제

• 6이상이 되는 첫번째 위치값은 7이다.
  

• 다수의 동일한 값이 있을 경우?
  : 맨 앞의 포인터를 반환함.
  

• end- 1 값과 비교했는데, 값이 없을 경우에..
  
  -> 뺄셈 하면, v.size()가 반환됨.

upper_bound

: 찾으려고 하는 key보다 초과하는 첫번째 위치