숫자 카운팅(이진탐색)

문제 설명

---

배열에 오름차순으로 N개의 숫자가 저장되어 있다.
M개의 탐색할 숫자가 주어질 때, 각 숫자가 배열에 몇 개씩 저장되어 있는지 출력하는 프로그램을 작성하시오.

입력 설명

---

첫째 줄에 N 이 입력된다. (1≤N≤200,000)
둘째 줄에 배열에 저장 되어있는 N개의 숫자가 순서대로 공백으로 구분되어 입력된다.
셋째 줄에 M 이 입력된다. (1≤M≤200,000)
넷째 줄에 M개의 탐색할 숫자가 순서대로 공백으로 구분되어 입력된다.
(이 숫자는 정렬 되어있지 않다)

출력 설명

---

입력 넷째 줄에서 주어진 탐색할 숫자의 배열 내 저장된 개수를 차례대로 출력한다.

입력 예시

---

10
1 1 1 6 9 11 13 17 19 20
2
1 9

출력 예시

---

3 1

#include <stdio.h>
#define MAX ((int)2e5)
int N;
int A[MAX+10];
int M;
int B[MAX+10];
 
int BinarySearchLower(int s, int e, int d){
    int sol=-1;
    while (s<=e){
        int m = (s+e)/2;
        if (A[m] == d){
            sol = m;
            e = m-1;
        }
        else if (A[m] > d){
            e = m-1;
        }
        else {
            s = m+1;
        }
    }
    return sol;
}
 
int BinarySearchUpper(int s, int e, int d){
    int sol=-1;
    while (s<=e){
        int m = (s+e)/2;
        if (A[m] == d){
            sol = m;
            s = m+1;
        }
        else if (A[m] > d){
            e = m-1;
        }
        else {
            s = m+1;
        }
    }
    return sol;
}
 
void Solve(void){
    for (int i=0; i<M; i++){
        int lower = BinarySearchLower(0, N-1, B[i]);
        if (lower != -1){
            int upper = BinarySearchUpper(0, N-1, B[i]);
            B[i] = upper - lower + 1;
        }
        else{
            B[i] = 0;
        }
    }
}
 
void InputData(void){
    scanf("%d", &N);
    for(int i=0 ; i<N ; i++) {
        scanf("%d", &A[i]);
    }
    scanf("%d", &M);
    for(int i=0 ; i<M ; i++) {
        scanf("%d", &B[i]);
    }
}
 
void OutputData(void){
    for(int i=0 ; i<M ; i++) {
        printf("%d ", B[i]);
    }
}
 
int main(void){
    InputData();
    Solve();
    OutputData();
    return 0;
}