# 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:

1. There is an increasing array $$A$$ of size $$n_1$$

2. 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?

• Can you credit the original source where you encountered this task?
– D.W.
Apr 5 at 7:45
• @D.W. Сlosed group on codeforce from the university Apr 5 at 7:49
• Your hypothesis states that $A$ and $M$ are the same size $n$, but that is not the case in your example. Which is it? Also, are there hypotheses about the values in $A$? (if they are positives integers, there is an algorithm in $O(n+\max(A))$.) Apr 5 at 8:50
• @Nathaniel Sizes may be different, but within certain limits, I wrote inattentively, sorry. All values in both arrays are within $[1, 10^7]$ and are integers Apr 5 at 9:10
• @Nathaniel There is also an idea to try to somehow minimize the number of read cache lines per request Apr 5 at 9:18

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.
• 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 $$);
• browse $$M$$; for $$m \in M$$, if $$m > \max(A)$$, return $$n_1$$, else return $$B[m]$$.