给定一个排序数组和一个正整数k，求出1 <= i <= k的区间(100(i-1)/k，100(i)/k]内的整数个数

Question

给定排序数组A1..n和正整数k，对1 <= i <= k的区间(100(i-1)/k，100(i)/k]中的整数个数进行计数，并将其存储在另一个数组G1..k中。

假设数组G已经被创建(不是算法中的输入)，并且G中的元素被初始化为0。

还有一个辅助函数Increase(i，count)，用于找出Ai对应的间隔(G)，并将G的值增加count；

例如，排序数组1,11,25,34,46,62,78,90,99，k=4

因此结果应该是G1 = 3，G2 = 2，G3 = 1，G4 =3，其中G1是一个间隔(0,25] G2 -> (25,50] G3 -> (50,75] G4 -> (75,100))

有没有什么分而治之的算法来解决这个问题？而不是线性地解决它？

更高级:另外，如果我们不能直接访问数组A中的元素，并且如果Ax和Ay在相同的间隔内，有一个函数Compare(x，y)返回true。如何解决？我是否可以尝试使每个组呼叫的时间增加至多log次，并且有k个组，因此运行时间为O(k log )？

我在这一点上的观察:如果Ai和Ay在i< y的同一区间内，则i

Answer 1

最简单的次线性方法(假设k << n)是进行(k+1)二进制搜索，每个边界值一个，产生一个近似(k lg n)-comparison算法。

通过智能地将探针组合在一起，可以将其降低到大约(k (1 + lg (n/k)。