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?
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 &lt; 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.