I came across an algorithmic problem. I do not know how to do it optimally.
The problem is as follows:
There is an increasing array $A$ of size $n_1$
There is an array $M$ of queries of size $n_2$
where $1 \le n_1, n_2 \le 10^7$
For each query element $m \in M$, it is required to find the count of elements in array $A$ that are strictly less than the query element $m$.
$A = [1,2,3,5]$
$M = [4,2]$
for $m = 4$ answer $3$
for $m = 2$ answer $1$
My idea works for a $O(nlogn)$. The algorithm is simple; for each request I do a binary search in array $A$. But can it be faster? Maybe B-tree?