可用分押宝游戏火热进行中...	专题改版：Java Web 专题

谁能给我一个好的算法！！多谢!!!!

楼主biaozhun1235（）2006-12-26 15:23:24 在 Java / J2SE / 基础类提问

int[] iArray ={ 1, 5, 9, 14, 27, 39, 41, 50, 345, 346, 348, 349, 981, 1207, 8721 };

int arg = 345;

我想利用一个算法快速的求出数组中大于arg（345）但最接近的值，即346。
谁能帮帮我，满分送上。。。问题点数：100、回复次数：37Top

1 楼biaozhun1235（）回复于 2006-12-26 15:25:10 得分 0

不好意思应该是

int[] iArray ={ 1, 5, 9, 14, 27, 39, 41, 50, 346, 348, 349, 981, 1207, 8721 };

里面没有345Top

2 楼fool_leave（请及时结贴）回复于 2006-12-26 15:37:53 得分 0

排序,然后二分法查找Top

3 楼caesarx（恺撒）回复于 2006-12-26 15:42:09 得分 0

public class Test {
public static void main(String[] args)
{
int[] iArray ={ 1, 5, 9, 14, 27, 39, 41, 50, 345, 346, 348, 349, 981, 1207, 8721 };

int arg = 345;

for(int i = 0;i < iArray.length;i++)
if((arg-arr[i]) < 0)
{
System.out.println(arr[i]);
break;
}
}
}
虽然不是什么算法，不过挺简单。Top

4 楼biaozhun1235（）回复于 2006-12-26 15:51:42 得分 0

不好意思，我的数组是排好序的，并且我的记录有上千条，在此只是做个示范，如果循环比较它速度太慢，二分法我觉得查找一个与345相等的值很快，但怎样利用二分法来查找大于它并且最接近的值呢？Top

5 楼seesea10523（）回复于 2006-12-26 15:51:56 得分 0

看你的数组好像是从小到大排序的，我的想法是用你的参数arg(这里的345)覆盖iArray[0]，让后把数字进行一次快速排序(这里只需要递归一次：就是让345找到自己的位置)，取数组中345后面的那个元素。这样应该是最快的Top

6 楼axman（江渚渔樵）回复于 2006-12-26 15:54:02 得分 0

利用二分查找得到它返回的索引后只需一步就可以算出来了.
你要的值就是 iArray[Math.abs(Arrays.binarySearch(iArray,arg))-1];
二分查找时如果找不到返回的是比它小的那个值的索引+2的负值.
所以只要取正再减1就是比它大的那个值的索引.Top

7 楼biaozhun1235（）回复于 2006-12-26 16:01:20 得分 0

seesea10523() ：
谢谢，能否帮我把程序写出来。。。。。Top

8 楼biaozhun1235（）回复于 2006-12-26 16:06:16 得分 0

axman(江渚渔樵) ：
谢谢，我的数组里是没有arg(345)的。。。。

还有大家能否不要用JAVA的Array中的方法，其实我是用在javascript里的，javscript的Array功能很少。。。。在此只是求个算法。。。Top

9 楼imA（男的不会，会的不男）回复于 2006-12-26 16:06:35 得分 0

定义一个存储绝对差值的变量abs，别且给abs赋值一个比较大的初始值（比如是MaxInteger)，定义一个索引位置index，赋值为0。
然后循环这个数组，用给定的值345飞别和每个元素做差值，判断差值与abs的绝对值大小，如果当前的差值小于abs，则把当前差值赋值给abs，并且将当前数组的索引值赋值给index，这样一次循环下来就可以知道最接近的值在数组的什么位置了，当然也就知道最接近的值是什么了。Top

10 楼ChDw（米）回复于 2006-12-26 16:10:26 得分 0

JDK已经写好了啊

int[] iArray ={ 1, 5, 9, 14, 27, 39, 41, 50, 346, 348, 349, 981, 1207, 8721 };
int num = 346;
int index = Arrays.binarySearch(iArray, num);
if(index < 0)
System.out.println(index + ":" + iArray[Math.abs(index + 1)]);
else
System.out.println(index + ":" + iArray[index]);
Top

11 楼ChDw（米）回复于 2006-12-26 16:11:41 得分 0

哦，上面的代码没有判断当num大于8721的情况，你要再处理一下Top

12 楼buyaowen（失业中，请勿打扰）回复于 2006-12-26 16:28:37 得分 0

给三个星的吧
学习了，我还想自己弄二分查找呢Top

13 楼biaozhun1235（）回复于 2006-12-26 16:56:24 得分 0

注意。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
注意。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
注意。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
注意。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

我的数组里没有345，并且数组里面永远不可能有345，请不要用JAVA中的Array里的方法，还有我的记录有上千条，也请不要用把整个记录循环一边的方法，我现在要的是效率，我目前的实现如下：

public class ErFenFa {
int[] iArray ={ 1, 5, 9, 14, 27, 39, 41, 50, 346, 348, 349, 981, 1207, 8721 };

int iSeek = 345;
int iCount = 0;

public int find()
{
int iIndex = 0;
int iStart = 0;
int iEnd = iArray.length - 1;

while (true) {
iCount++;
iIndex = (iStart + iEnd) / 2;

if (iArray[iIndex] < iSeek) {
iStart = iIndex;
} else if (iArray[iIndex] > iSeek) {
iEnd = iIndex;
break;
}
//注：我就写到这里，下面准备这样写。。
我现在是采用二分法的思想，找出一个小于345但离它最近的索引，再找出一个大于345的索引（但可能不是最近的），然后根据小索引大索引把iArray截取小索引与大索引中间的数据，然后再利用大家说的计算差值或者其他方法，不过这样做还是要循环一边，如果我的记录有2000条，通过这个方法可以得出500条，但是循环500条还是很慢啊，所以请各位想一个高效的方法。。。
return iCount;
}
}Top

14 楼seesea10523（）回复于 2006-12-26 17:17:13 得分 20

public int getValue(int[] array,int arg, int positionA, int positionB){
if (positionA>=positionB) return positionA;

int m = (positionA+positionB)/2
if(int[m] < arg){
return getValue(array,arg,m,positionB);
}esle if(int[m] > arg){
return getValue(array,arg,positionA,m);
}else if(int[m] = arg){
return m+1;
}
}

int[] iArray ={ 1, 5, 9, 14, 27, 39, 41, 50, 346, 348, 349, 981, 1207, 8721 };

int iSeek = 345;
getValue(iArray ,iSeek ,0,iArray.length);

用下递归，二分查找不知道速度怎么样Top

15 楼ChDw（米）回复于 2006-12-26 17:20:56 得分 0

你根本没有跑我的代码！我写的代码是非常正确的运行的！

Arrays.binarySearch就已经考虑到了找不到该成员的情况了！Top

16 楼ChDw（米）回复于 2006-12-26 17:23:11 得分 20

如果你认为永远不存在345的情况，你只要认定index一定小于0就行了
int[] iArray ={ 1, 5, 9, 14, 27, 39, 41, 50, 346, 348, 349, 981, 1207, 8721 };
int num = 345;
int index = Arrays.binarySearch(iArray, num);
System.out.println(index + ":" + iArray[Math.abs(index + 1)]);

Arrays.binarySearch会返回 (-(insertion point) - 1)，也就是346的位置Top

17 楼ljq164621155（）回复于 2006-12-26 17:48:27 得分 0

哎呀...我对大学写的代码还有点不懂...你们在写代码的时候是否可以给上注释..这样让一些莱鸟容易看懂...谢了Top

18 楼ChDw（米）回复于 2006-12-26 17:56:14 得分 0

这里唯一特别点的就binarySearch吧，从名字就看出来是二分查找方法，

它返回小于0就是没有找到并返回的意义代表：(-(insertion point) - 1)
Top

19 楼hxl_521（）回复于 2006-12-26 18:03:31 得分 0

哎呀...我对大学写的代码还有点不懂...你们在写代码的时候是否可以给上注释..这样让一些莱鸟容易看懂...谢了
------------------------------------------
支持哦，因为我也菜鸟！希望大家能体谅我们，谢谢！Top

20 楼buyaowen（失业中，请勿打扰）回复于 2006-12-26 18:31:02 得分 0

去看api，然后回来说话。
带星的基本上不会骗人的Top

21 楼ROCK001（）回复于 2006-12-26 20:02:58 得分 0

小弟发表下看法，说的不好大家指教：
按照楼主的意思。感觉前面就用2分法，根据数组的个数大概确定下范围后，用快速排序来进行排序，这样应该是效率最快的吧。（单纯的2分法按照楼主的要求好象不是最快的）Top

22 楼wanguanghai（心灵鸡汤）回复于 2006-12-26 20:28:53 得分 0

折半查找Top

23 楼xiaofengsuilu（）回复于 2006-12-26 21:39:56 得分 0

支持ChDw(米)
楼主应该好好考虑别人的建议Top

24 楼chenqing1128（Alex）回复于 2006-12-26 22:37:01 得分 0

先考虑极端的情况,
使用2分法.不过是个变动版.本来比较的时候是取中间一个与345比.现在要改为在比较的时候先如下比较
如果第一个大于345,就取第一个.
如果最后一个小于345就没有结果.
否则才取中间一个比较,决定下一步的走向(即取前半段还是后半段).

如此递归即可.
Top

25 楼zhangfan790913（笑月）回复于 2006-12-26 22:52:41 得分 0

晕结果不是都有了吗?
楼主怎么就是不同意呢?

怪Top

26 楼chenqing1128（Alex）回复于 2006-12-26 22:53:10 得分 0

补充一点:在做中间比较的时候.
如果中间值(以下简称中值)大于345取前半段.同时保存中值.如果前半段没有结果就返回中值.
Top

27 楼chenqing1128（Alex）回复于 2006-12-26 22:53:47 得分 0

先考虑极端的情况,
使用2分法.不过是个变动版.本来比较的时候是取中间一个与345比.现在要改为在比较的时候先如下比较
如果第一个大于345,就取第一个.
如果最后一个小于345就没有结果.
否则才取中间一个比较,决定下一步的走向(即取前半段还是后半段).

如此递归即可.

补充一点:在做中间比较的时候.
如果中间值(以下简称中值)大于345取前半段.同时保存中值.如果前半段没有结果就返回中值.
Top

28 楼qsrock（）回复于 2006-12-26 22:57:02 得分 0

学习了!~
应该用二分查找比较快!~Top

29 楼2000paladin（红黑骑士）回复于 2006-12-26 23:59:05 得分 40

public static int seek(int[] array, int arg, int sIndex, int eIndex) {

int sIdx = sIndex;
int eIdx = eIndex;
int tmpIdx = 0;
while (true) {
tmpIdx = (sIdx + eIdx) / 2;
if (sIdx == tmpIdx || eIdx == tmpIdx)
break;
if (arg > array[tmpIdx]) {
sIdx = tmpIdx;
} else {
eIdx = tmpIdx;
}
System.out.println(sIdx + " - " + eIdx);
}

return arg < array[sIdx] ? array[sIdx] : array[eIdx];

}
public static void main(String[] args) {
int[] arr = { 1, 5, 9, 14, 27, 39, 41, 50, 346, 348, 349, 981, 1207,
8721 };
System.out.println(Search.seek(arr, 345, 0, arr.length - 1));

}

这个就找它的索引,当范围缩小到两个时停止.然后第一个如果比arg大则返回第一个,否则返回第二个.Top

30 楼w_anthony（）回复于 2006-12-27 00:04:19 得分 0

不知道转换问题么？

你把题目改成把345插到数组中，插入的位置+1不就是你要的结果了。

怎么插方法很多把，二分、堆排序之类的都可以阿Top

31 楼shuyanbo（楚国壮士）回复于 2006-12-27 11:37:24 得分 0

没有必要吧，从头到尾走一遍，比较差值，记住索引值不就完了，复杂度就是O（n)Top

32 楼sweetbai（）回复于 2007-03-08 22:19:35 得分 0

ChDw(米) ( ) 信誉：155 Blog 2006-12-26 17:23:11 得分: 0

如果你认为永远不存在345的情况，你只要认定index一定小于0就行了
int[] iArray ={ 1, 5, 9, 14, 27, 39, 41, 50, 346, 348, 349, 981, 1207, 8721 };
int num = 345;
int index = Arrays.binarySearch(iArray, num);
System.out.println(index + ":" + iArray[Math.abs(index + 1)]);

Arrays.binarySearch会返回 (-(insertion point) - 1)，也就是346的位置

高手。。。瞻仰ing。。。Top

33 楼oDon（孤独绑定）回复于 2007-03-08 22:27:08 得分 0

二分查找吧Top

34 楼seavers（泪魂）回复于 2007-03-08 22:37:11 得分 0

JDK源码, 贴出来, 方便一些

/**
* Searches the specified array of ints for the specified value using the
* binary search algorithm. The array must be sorted (as
* by the {@link #sort(int[])} method) prior to making this call. If it
* is not sorted, the results are undefined. If the array contains
* multiple elements with the specified value, there is no guarantee which
* one will be found.
*
* @param a the array to be searched
* @param key the value to be searched for
* @return index of the search key, if it is contained in the array;
* otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
* <i>insertion point</i> is defined as the point at which the
* key would be inserted into the array: the index of the first
* element greater than the key, or <tt>a.length</tt> if all
* elements in the array are less than the specified key. Note
* that this guarantees that the return value will be >= 0 if
* and only if the key is found.
*/
public static int binarySearch(int[] a, int key) {
return binarySearch0(a, 0, a.length, key);
}

// Like public version, but without range checks.
private static int binarySearch0(int[] a, int fromIndex, int toIndex,
int key) {
int low = fromIndex;
int high = toIndex - 1;

while (low <= high) {
int mid = (low + high) >>> 1;
int midVal = a[mid];

if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}Top

35 楼chllcy（搬张小板凳,听星星们的高见）回复于 2007-03-08 22:47:00 得分 0

学习了不过System.out.println(index + ":" + iArray[Math.abs(index + 1)]); 里面的index应该也加个绝对值不然是负的Top

36 楼huruihappy（）回复于 2007-03-08 22:54:26 得分 0

循环500次还是慢了点楼主试下用树或者hashTable来做下 ,学校要断电了明天早上来发发.Top

37 楼javatalk（）回复于 2007-03-08 23:12:33 得分 20

public class BinarySearch {
public static void main(String[] args) {
int[] iArray ={1,5,9,14,27,39,41,50,346,348,349,981,1207,8721};
int n = 345;
System.out.println(binarySearch(iArray,n));
}
static int binarySearch(int[] num,int n) {
int startidx = 0;
int endidx = num.length-1;
int index = 0;
boolean found = false;
while(startidx<=endidx && !found) {
index = (startidx+endidx)/2;
if(num[index]<n) {
startidx = index + 1;
} else if(num[index]>n) {
endidx = index -1;
} else {
found = true;
break;
}
}
if(!found){
if(endidx<0){
return 0;
} else if(startidx>=num.length){
return num.length-1;
} else if(num[startidx]-n>n-num[endidx]){
return endidx;
} else {
return startidx;
}
} else {
return index ;
}
}
}Top