[#3] header <algorithm> - lower_bound, upper_bound

 lower_bound, upper_bound 

• c++에서는 이진 탐색으로 원소를 탐색하는 lower_bound, upper_bound 함수를 제공한다.
• lower_bound는 찾고자 하는 원소 값의 시작주소 반환 (iterator)
• upper_bound는 찾고자 하는 원소 값의 마지막주소 반환 (iterator) 

 

 

사용 예

코드

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

void Input(int& Data) { cin >> Data; }
int  Counting(vector<int>& Base, const int TARGET);

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n = 0;      // 상근이가 가지고 있는 카드 수
	int m = 0;      // 찾아야 하는 카드 수
	int target = 0; // 찾아야하는 카드 번호

	cin >> n;
	vector<int> cards(n);
	for_each(cards.begin(), cards.end(), Input);  // 상근이 카드 입력 받기
	sort(cards.begin(), cards.end(), less<>());   // ASC Sort


	cin >> m;
	for (int i = 0; i < m; ++i)
	{
		cin >> target;
		cout << Counting(cards, target) << ' ';
	}
	return 0;
}

int Counting(vector<int>& Base, const int TARGET)
{
	int min = lower_bound(Base.begin(), Base.end(), TARGET) - Base.begin();
	int max = upper_bound(Base.begin(), Base.end(), TARGET) - Base.begin();
	int result = 0;
	for (int i = min; i < max; ++i)
		++result;
	return result;
}

 

 

---