从数组中,设定寻求最合适的10%区间,可以包含最多的数据

来源：百度知道 编辑：UC知道 时间：2024/06/25 11:54:22
例如我有一系列的数据-9.3,8.56,-3,-3.5,-5,-3,-3.2,5.1,3.5,3.2,5.2,9.3,-2.1,-3.5,-4.2,-6.2,-8.6,-3.15,6.32,6.32. 可能是N多数据.不固定的.
我现在想设定一个范围,例如-3,7 或者 -4,6, 或者-3.7,6.3
让这个范围包括最多的数字
加入,我共有1500组数据,如果我设定-3,7 这个范围,可能包括1102组数据,如果设定-3.5,6.5可能包括1135组数据.我现在该如何知道怎么设置这个最优的数据范围???
设定的数据,绝对值之和必须是10,如-3,7 -2.8,7.2

应该是取区间[a,b]，其中b-a=10吧。但闭区间还是开区间呢？我是按照闭区间做的。
方法：先排序，再从小到大依次查找，查找使用两分法。
复杂度：O（nlogn）
输入：依次输入n个实数，以空白符间隔，非数字输入表示结束。
输出：最优区间和区间里的数据量。
下面是源程序。

#include <iostream>
using namespace std;

int n;
double data[1500];

/* 在[ data[from],data[to] ]之间,找到最大的mid,使得data[mid]<value */
/* 这个函数做得通用了点，具体到这个问题其实只要一个from参数就可以了 */
int BSearch(int from,int to,double value){
int mid;
//先两分查找
while(from<=to){
mid=(from+to)/2;
if(data[mid]==value){
to=mid;
break;
}
if(data[mid]>value)
to=mid-1;
else
from=mid+1;
}
/*此时,data[to]<=value<=data[from],且from-to=1
或者data[to]=value*/

//可能有相同的数字
while(to<n && data[to+1]==data[to])
to++;
return to;
}

int cmp_double(const void *in1,const void *in2){
return (*(double*)in1 < *(double*)in2)? -1 : 1;
}

int