Number Card Problem (Binary Search)

  This Problem was introduced on the BackJoon Algorithm Website.

Problem : 

There are two different types of card sets.

The first set contains an N number of cards and it can have the same number of cards more than once. 

The second set has a K number of cards and the problem is to find how many cards do first set has that are the same as the second set. 

If the first set has more than one same card, then count all of them and save them into the list or array.

Due to the time limit, I had to change a code a little bit different than an ordinary binary search. 

If the first set has more than one same card, then do the followings:

- First: Find lower bounds

- Second: Find upper bounds

- Thrid : Subtract lower bounds from upper bounds

Input :

10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10

Expected output :

3 0 0 1 2 0 0 2

#include <iostream>

#include <algorithm>

using namespace std;

int N, M;

int cards[500000];

int lowerBound(int n)

{

int f = 0, l = N - 1, m;

for (;;)

{

m = (f + l) / 2;

if (f > l)

{

if (cards[f] == n) return f;

else return -1;

}

if (cards[m] >= n) l = m - 1;

else f = m + 1;

}

}

int upperBound(int n)

{

int f = 0, l = N - 1, m;

for (;;)

{

m = (f + l) / 2;

if (f > l)

{

if (cards[l] == n) return l;

else return -1;

}

if (cards[m] <= n) f = m + 1;

else l = m - 1;

}

}

int main(void)

{

cin.tie(NULL);

ios::sync_with_stdio(false);

cin >> N;

for (int i = 0; i < N; i++)

cin >> cards[i];

sort(cards, cards + N);

cin >> M;

int n, res;

for (int i = 0; i < M; i++)

{

cin >> n;

res = upperBound(n);

if (res == -1) cout << "0 ";

else cout << res - lowerBound(n) + 1 << " ";

}

return 0;

}

####################################################################

Problem Source: https://www.acmicpc.net/problem/10816

My Github:  https://github.com/AdvancedUno/AlgorithmProblems/tree/main/Binary_Search/NumberCard