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