Given a sorted array and a positive integer k, find the number of integer in the interval(100(i-1)/k, 100(i)/k] for 1 <= i <= k

Question

Given a sorted array A[1..n] and a positive integer k, count the number of integer in the intervals(100(i-1)/k, 100(i)/k] for 1 <= i <= k and store it in another array G[1..k]

Assume array G is already created(is not an input in the algorithm ) and element in G is initialized to be 0.

Also, there is a helper function Increase(i, count) to find the interval(G[?]) of A[i] correspond to and increase the value of G[?] by count;

For example, a sorted array [1,11,25,34,46,62,78,90,99] and k = 4

so the result should be G[1] = 3, G[2] = 2, G[3] = 1, G[4] = 3 where G[1] is an interval (0,25] G[2] -> (25,50] G[3] -> (50,75] G[4] -> (75,100]

Is there any divide-and-conquer algorithm to solve this problem? rather than solve it linearly?

More advanced: Also, If we cannot directly access the element in array A , and there is a function Compare(x, y) to return true if A[x] and A[y] is in the same interval. How to solve it? Can I try to make each group call at most log n time Increase and there are k groups hence having O(k log n ) running time?

My observation at this point: if A[i] and A[y] is in the same interval where i < y, element A[j] with i < j < y will also in the same interval.

• Stef: Linear is okay ;) Note that it's impossible to do better than linear if you intend to "see" all elements in the array, since that already takes a linear time.
• D.W.: cs.stackexchange.com/q/130666/755

Answer 1

The easiest sublinear approach (assuming k << n) is to do (k+1) binary searches, one for each boundary value, yielding an approximately (k lg n)-comparison algorithm.

This can be lowered to approximately (k (1 + lg (n/k))) by combining probes together intelligently.