Fastest way to find the number of elements in a range
Given an array with n elements
, how to find the number of elements greater
than or equal
, for a given value (x)
in a given range index i to index j
in O(log n)
or better
complexity?
my implementation is like this, but this O(n)
for(a=i;a<=j;a++)
if(p[a]>=x) // p[] is array containing n elements
count++;
source to share
If you are allowed to preprocess the array, then from O(n log n)
preprocessing time we can respond to any request [i,j]
at O(log n)
.
Two ideas:
1) Please note that this is enough to answer inquiries [0,i]
and [0,j]
.
2) Use a binary balanced order steady state statistics tree that supports n versions of the tree, version i is generated from version i-1 by adding [i] to it. To answer query([0,i], x)
, you are asking for the i version tree for cardinality > x
(mostly rank information). The order statistics tree allows you to do this.
*: persistent data structures are a nifty functional programming concept for immutable data structures and have efficient algorithms for constructing them.
source to share
If the array is sorted, you can find the first value less than X with a binary search, and the number of elements greater than X is the number of elements after that element. It will be O (log (n)).
If the array is not sorted, there is no way to do this in less than O (n) time, since you will have to examine each element to check if it is greater than or equal to X.
source to share
Not possible in O (log N) because you need to check all items, so an O (N) method is expected.
The standard algorithm for this section is based on the quick sort, sometimes called a quick choice .
The idea is that you are not sorting the array, but just split the section containing x and stop when x is your pivot element. At the end of the procedure, you have all elements of x and more to the right of x. This is the same procedure as for finding the kth largest element.
Read about a very similar problem in How do I find the kth largest element in an unsorted array of length n in O (n)? ...
The index of requirements i to j is not a constraint that introduces any complexity into the problem.
source to share
Given your requirements, where the data is not sorted ahead of time and is constantly changing between requests, O (n) is the best complexity you can hope to achieve as there is no way to count the number of items greater than or equal to some without looking at them.
It's pretty straightforward if you think about it: you can't avoid checking every element of a range for any type of search if you have no idea how it's presented / ordered in advance.
You can build a balanced binary tree, even sorting by radius on the fly, but you're just pushing the overhead elsewhere to the same linear or worse, linear-linear complexity O (NLogN), since such algorithms will check each element again in the range to sort it.
So there is nothing wrong with O (N) here. This is ideal, and you are looking at either changing the entire nature of the data that is involved externally to allow it to be sorted efficiently ahead of time, or micro-optimizing (eg: parallel fors to handle multi-threaded subranges, provided they are "short enough) to tweak his.
In your case, your requirements seem tough, so the latter seems like the best choice with a profiler.
source to share