给定一个排序数组a[1..n]和一个正整数k，计算区间(100(i-1(/k，100(i(/k]中的整数个数，表示1<=i<=k，并将其存储在另一个阵列G[1..k]中
假设数组G已经创建(不是算法中的输入(并且G中的元素被初始化为0。
此外，还有一个辅助函数Increase(i，count(，用于查找a[i]的区间(G[？](，并将G[？】的值增加count；
例如，排序数组[1,11,25,34,46,62,78,90,99]和k=4
所以结果应该是G[1]=3，G[2]=2，G[3]=1，G[4]=3其中G[1]是区间(0,25]G[2]->(25,50]G[3]->(50,75]G[4]->(75100]
有什么分而治之的算法可以解决这个问题吗？而不是线性求解？
更高级：此外，如果我们不能直接访问数组A中的元素，并且如果A[x]和A[y]处于同一区间，则有一个函数Compare(x，y(返回true。如何解决？我可以尝试在最多log n时间进行每个组调用吗？增加了k个组，因此运行时间为O(k log n(？
我在这一点上的观察：如果A[i]和A[y]在相同的区间中，其中i<y、 元素A[j]，其中i<j<y也将处于相同的间隔中。
最简单的次线性方法(假设k<<n(是进行(k+1(个二进制搜索，每个边值一个，产生近似(k-lgn(的比较算法。
这可以通过智能地将探针组合在一起而降低到大约(k(1+lg(n/k((。