[PS][이분탐색]/[BOJ][10816][숫자 카드2]

boj10816.cpp

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

int n,m,t;
int card[500000];
int s, e, mid;
int maxRight, minLeft;

int main(void) {
	cin.tie(NULL);
	ios::sync_with_stdio("false");
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> card[i];
	}
	cin >> m;
	sort(card, card + n);
	
	while(m--){
		cin >> t;

		minLeft = n;
		maxRight = -1;
		
		//t보다 큰 가장 작은 index 찾기
		s = 0;
		e = n - 1;
		while (s <= e) {
			mid = (s + e) / 2;
			if (card[mid] < t) {//t보다 작은 조건에 맞으면
				maxRight = mid;//s를 키워서 범위 줄이기
				s = mid + 1;
			}
			else {
				e = mid - 1;
			}
		}

		//t보다 작은 가장 큰 index 찾기
		s = 0;
		e = n - 1;
		while (s <= e) {
			mid = (s + e) / 2;
			if (card[mid] > t) {//t보다 큰 조건에 맞으면
				minLeft= mid;//e를 줄여서 범위 줄이기
				e = mid - 1;
			}
			else {
				s = mid + 1;
			}
		}
		cout << minLeft - maxRight - 1 << " ";
	}
	return 0;
}