How can I make my algorithm more efficient? 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$.
For example:

$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?
If values in both arrays are positive integers, there is an algorithm in $O(n_1 + n_2 + \max(A))$. This algorithm is interesting if those three values are of the same order of magnitude.
The steps are as follow:

check last element of $A$ to know $\max(A)$;
create an array $B$ of size $\max(A)$;
browse $A$ and modify $B$ so that $B[i]$ represents the smallest index $j$ such that $A[j] \geq i$ (that means the number of elements of $A$ that are $&lt;i$);
browse $M$; for $m \in M$, if $m &gt; \max(A)$, return $n_1$, else return $B[m]$.