一个临界点的问题

Question

假设有一组值（大于等于0的数），总量级别：百万以上，需要求出总和在某个值（Y）的位置。实际情况中Y的值一般也是上万的。比如：有 5，2，0，3，4，6，7，1，11，3 等求在Y=12的位置，分析如下：值： 5，2，0，3， 4， 6， 7， 1，11，3累计：5，7，7，10，14，20，27，28，39，41此时临界点在第4个数【3】那。如果是10的话，位置也是第4个数。数据在数据库中，实际处理不考虑数据的排序问题，只需要从总量中找到一片数据总量接近或等于Y。请教有何算法可以快速定位到临界点的位置.已知道的算法，1，逐条累计，可能需要较长时间2，先按大到小排序，逐块累计，比上面快些。（操作是允许排序的）3，类似2分的算法，直接对半，累加前半数据比较，大的话再减少一半，小的话加上剩余的一半。无限2分，直至累计值与Y的接近或等于。这个算累计 我是在数据库ORACLE中做的。

Answer 1

1、原始表：
t_bill;字段:索引ID（number）,分钟值talktime（varchar(40)）;
2、递归累加生成表：
t_bill_2 ;字段:索引ID（number）,分钟值talktime（varchar(40)）;

递归累加生成表 talktime建立索引

两个表的id一样；

3、可以考虑根据递归累加生成表的talktime分表； 比如1--1000的在1表，依次类推；

4、根据根据Y值查分表编号，然后查

Answer 2

两个数比较比加运算要省时间，尽量减少加的运算次数，已知Y的值，那么也就是说必须一个一个计算累加到Y附近，这个运算至少要进行一次，则1和2的方法比3要快，最好是从大到小排序，这么的话尽量少的加运算就可以累加到Y值。

Answer 3

假设有一组值（大于等于0的数），总量级别：百万以上，需要求出总和在某个值（Y）的位置。实际情况中Y的值一般也是上万的
1.
(1000000个数的和) / 1000000 = 一百万的数的平均值
2.
Y / 一百万的数的平均值=等于大约需要累加多少数，然后以这个位置开始判断
3
相差值不大的话就慢慢比较，比较大的话，就从这个位置开始，按步骤1，继续

Answer 4

1.(1000000个数的和) / Y = 以这个数为步长 
2 每次按这些这个步长 把数加起来和Y比较
相差不大就一个个慢慢比较 相差大的话 跳转到1 ，按1方法比较。

这个问题的任何方法都只能是O(N) 
但是我说的方法二能比较快的接近。

jinnianshilongnian 
第三方用到数据库.....，这个。。。呵呵