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

Question

int[] iArray ={ 1, 5, 9, 14, 27, 39, 41, 50, 345, 346, 348, 349, 981, 1207, 8721 };int arg = 345;我想利用一个算法快速的求出数组中大于arg（345）但最接近的值，即346。
谁能帮帮我，满分送上

Answer 1

不好意思应该是int[]  iArray  ={  1,  5,  9,  14,  27,  39,  41,  50,  346,  348,  349,  981,  1207,  8721  };  里面没有345

Answer 2

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;
}
}
}
虽然不是什么算法，不过挺简单。

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

axman(江渚渔樵) ：
谢谢，我的数组里是没有arg(345)的。还有大家能否不要用JAVA的Array中的方法，其实我是用在javascript里的，javscript的Array功能很少。 在此只是求个算法

Answer 7

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

Answer 8

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]);

Answer 9

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

Answer 10

注意。。
注意。。
注意。。
注意。。  我的数组里没有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;
   }
}

Answer 11

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);
用下递归，二分查找不知道速度怎么样

Answer 12

你根本没有跑我的代码！我写的代码是非常正确的运行的！Arrays.binarySearch就已经考虑到了找不到该成员的情况了！

Answer 13

如果你认为永远不存在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的位置

Answer 14

这里唯一特别点的就binarySearch吧，从名字就看出来是二分查找方法，它返回小于0就是没有找到并返回的意义代表：(-(insertion point) - 1)

Answer 15

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

Answer 16

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

Answer 17

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大则返回第一个,否则返回第二个.

Answer 18

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

Answer 19

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 &gt;= 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.
    }

Answer 20

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

Answer 21

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

Answer 22

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 ;
}
}
}