有点难可以加分,数组的某一段要平均分段,快速求数组下标!

Question

数组A[]:
大小约1M,类型integer, a[n+1]>=a[n]区间 b,c:
类型double;b,c的值为数组中某一元素的值,或者某两个元素值中间的某个值
现在将区间bc,分成d等分,每等分的宽度是e:=(b-c)/d  (double),这里可假设e:=100;求每个等分开始或者结束时的数组下标,结果放在另一个数组中,如果结果不是整数,可以trunc取整
简单的办法是二分法搜索,本题目由于是多个区间搜索,有一定规律,所以要求快一些提供算法即可,可以不是具体代码,要求代码运行速度

Answer 1

不太明白。b,c是数组中元素的值？元素没有重复的？
如果是这样，可以先用二分法查找到b,c对应元素的下标，然后就好办了，直接根据b,c间元素的个数算出e，再一个个加e就行了。

Answer 2

总  数: S = 98
分五段: N =  5
段  长: 
       Si = (S % N = 0)? (S div N) : (S div N + 1)
       if S % N = 0 then
         Si = S div N
       else
         Si = S div N + 1;
第Ｉ段(I从1起始,下标从0起始): 
      STARTi = Si * (I - 1)
      ENDi   = Min(Si * I - 1, S - 1)

Answer 3

举例:数组值:  2,3,3,4,5,6,7,7,8,9,10,11 
a[0]=2, a[11]=11,假设数组值区间:3.2--10.7,均分3部分
----上面是已知,下面是计算和结果,那么均分的界限就是:3.2-5.7-8.2-10.7对应的数组值取整后是 3,5,8,10,
求得数组下标为 a[2],a[4],a[8],a[10],
这个2,4,8,10就是目标值,有点难哦!!!

Answer 4

如果先不考虑极端情况，比如值不存在越界的话，大致的思路如下：1、除法N等分区间
2、等分值取整，存储在临时数组temp[]中
3、遍历temp[]
     二分查找temp[i]在A中的位置
     记录本次找到的位置
      下次搜索以本次找到的位置为开始区间二分
4、结束
      

Answer 5

1M的数据，查找一次最坏需要20次，查找n次最坏也就20*n（若考虑每次查找完后，将减少一次数据那更少），这个对于现在计算机应该不算什么吧！！！如果要再次减少查找速度，我倒是有个想法，但这个想法的可能与你的数据相关。以你例子为例,
若 均分的界限为:3.2--10.7,均分3部分 
那么均分的界限就是:3.2-5.7-8.2-10.7 
对应的数组值取整后是 3,5,8,10, 现在考虑数据大致是均分的。先找出 3和10的位置，得到的结果为a[2], a[10]，
由于要分为3个区间，则每个区间间隔为（10-2）/3=2.67
可以认为大致的区分为a[2],a[5],a[8]，a[10];然后确认猜测的中间区间是否正确，
先把a[2] a[8] 的作为一个区间来作2分查找来找5，若5这个数据不在a[2]，a[8]中，再取下一个区间找，如果数据大致均匀分布，这样的速度应该可以提高。

Answer 6

二分搜索没有什么问题啊，你这是排序好的数组，依我记忆，在这个情况下二分搜索的算法时间复杂度应该最少了（log2（n））
有重复的情况，那你的判断语句不要以 = 终止，而是以 a[n]=b and a[n-1]《b 为终止条件啊对于刚才提到的方法，实际上是吧你的数据假想为 y=ax+b 的线性数组，肯定会有偏差，只不过如果数据在这个偏差位不大的情况下，速度应该非常理想，
如果，数据少的时候那你就直接二分查找好了，如果数据少的话，应该不会造成太大的算法时间开销啊，只不过这个度你要掌握好，最好是写出来调试一下就知道了。