How do you find all integers in a sorted array of size n that appear n/k times, given that 0 < k < n, and in O(k log n) time?

Question

This looks like a typical divide and conquer algorithm, but with a few tricky parts.

It looks like we want to do k operations and divide the array in half at each step because of the O(k log n) restriction, but I'm confused about the specifics. When I try to come up with the algorithm, I think about making k comparisons with varying elements that are ceil(n/k) apart, but I don't see how recursively doing anything like that with broken up halves of the array would do anything beneficial.

Given this sorted array:

A = [1, 2, 3, 4, 4, 4, 4, 5]

If k = 1, then we do one comparison between A[0] and A[7] and we're done.

If k = 2, we can't do much because there's no good way to make 2 meaningful comparisons. And if we're going to split it in half and check again to fulfill the log(n) time requirement, the 4's would get split up.

Any ideas?

Answer 1

Let t = $\frac{n}{k}$

Set counter c = 0

Set variable s = 0

1.Check if A[s] == A[s + t-1]. (Since the array is sorted,
        this means that the first t elements are equal)

    2.1 If yes, check if A[s] != A[t+s]. (This is to ensure that there are 
    not more than t copies of A[s])

        3.1 If yes this means that the element A[s] occurs 
        exactly t times => Set c = c + 1

        3.2 If no, set s to the index of the first number in A, 
        which is greater than A[s] (you can do this using a slightly modified
        binary search in log(n) time)

    2.2 If no, set s to the index of the first occurrence of A[s + t-1]
    (again, you can do this in log(n) time using modified binary search)

You can check that the worst case for this algorithm is an array of the type

A = { 1, 2 ... 2, 3, 4 ... 4, 5, 6 ... 6, ... } where the numbers with ... appear t times. This is 2k - 1 binary searches so $O(k\log{}n)$

Answer 2

Let m = ceil [n/k], so you want numbers occurring m or more times. Since the array is sorted, if you check array elements a [m-1], a[2m-1], a[3m-1] etc. you find all the integers you want (and some you don't want).

So you start with x = a [m-1]. If x == a [2m-1] then you found a number, and you can remove a[3m-1], a [4m-1] etc. as long as they are equal to x.

If x != a [2m-1], then you use binary search to find the largest i from m-1 to 2m-2 that is equal to x, and check whether x = a [i - m + 1]. That's the idea, you have to be a bit careful to implement it.

Since at most you do k binary searches in subarrays of length m, the time is O (k log m) = O (k log (n / k)) which is quite a bit better than O (k log n) when k is large (and if k is small then the execution time is small anyway).

A bit more careful implementation: You want to find all integers in a sorted array that occur at least m times. Let's call these integers "heavy". Let c = 0; throughout the algorithm you have found all heavy numbers before a [c], and there is no array element before a [c] that is equal to a [c].

If c + m - 1 ≥ n then you are done. Otherwise let i = c + m - 1 and x = a [i]. There can be no element in a [c] to a [i - 1] that is heavy and different from x, so the question is whether x is heavy.

Let j = i; and as long as j + m < n and a [j + m] = x, let j = j + m. Use binary search to replace j with the largest index from j to min (j+m-1,n-1) containing an element equal to x. So now a [i] to a [j] are all equal to x, and there is no element at a [j+1] equal to x.

If j ≥ i + m - 1 or a [j - m + 1] == x then x is heavy. In any case, replace c with j + 1 and continue.

We increase c at least by m at the cost of one binary search in an array of length m or less, or we increase c by m again in constant time.

PS. You could improve the execution time slightly as follows: You always check for the last number in an interval of size m-1 which is equal to x. Depending on where that last number is found, the algorithm makes more or less progress. To improve the worst case, you replace binary search by something slightly less balanced that is faster when the result is at the left end of the interval, so that there is less work if there is less progress.