• 참고 자료 : https://chanhuiseok.github.io/posts/algo-55/

=> 이분탐색이다.

upper_bound와 lower_bound를 이용한 실용적인 것들

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;



//5를 만들수 있는 연속 수열 만들기
int main()
{
	vector<int>v = { 10,20,30,50,50,50,50,60,62,63,70,80 };
	sort(v.begin(), v.end());
	auto iter = lower_bound(v.begin(), v.end(), 50);
	auto iter2 = upper_bound(v.begin(), v.end(), 50);

	cout << "가장 앞에 위치한 50의 인덱스번호는 " << iter - v.begin() << endl;
	cout << "50의 개수는 "<< iter2 - iter << endl;
	cout << "50 이상인 원소의 개수는 "<< v.end() - iter << endl;
	
	auto iter3 = upper_bound(v.begin(), v.end(), 70);
	cout << "50에서 70까지의 개수는 " << iter3 - iter << endl;


}

lower_bound , upper_bound

• 오름차순이 되어 있는 상태에서 가능하다.
• 시간복잡도는 Log(n)

lower_bound

: 타겟으로 잡은 값을 컨테이너 중 시작원소의 반복자를 반환 받는다.

• target값이 없을때는 end()를 반환하는 것이 아니라 target보다 큰 값중 첫번째 원소를 리턴한다.
  

upper_bound

: 타겟으로 잡은 값을 컨테이너 중 마지막원소의 다음의 반복자를 반환 받는다.

-> 인덱스가 5가 나와야 하는데 upper_bound는 다음 반복자를 가리키므로
6이 나오는 것을 확인할 수 있다.

• 주의할점
  
  -> 다음 반복자 위치는 end()이므로 참조하려고 하니까 문제 발생한다.
  /+ 타겟으로 잡은 값이 없어도 end()를 반환한다.

• 안전하게 사용하기
  
  -> 변수로 받고 예외처리함으로써 사용하자
  

• 최종
  

몇번째에 인덱스에 있을까?

upper에서 문제가 되므로 반드시
데이터의 개수를 구할 때만 사용하자.
1. 컨테이너 중에서 4는 없으므로 0을 반환한다.

2. 컨테이너 중에서 1은 두개 있다.

3. 컨테이너 중에서 2는 3개 있다.

관련 문제

• 이코테 : 정렬된 배열에서 특정 수의 개수 구하기

중요한 사항들

• 50의 갯수는 몇개 있을까?
  

• 20,30,40은 몇개 있을까?
  

순차적으로 나열되어 있을때 ?? 이상의 갯수는?

-> lower_bound를 사용하자.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;



//5를 만들수 있는 연속 수열 만들기
int main()
{
	vector<int>v = { 10,20,30,20,50,50,50,50,60,70,80 };
	sort(v.begin(), v.end());
	auto iter = lower_bound(v.begin(), v.end(), 50);

	cout << iter - v.begin() << endl;
	cout << v.end() - iter;
}