在数字列表中找到最接近的数字

Question

我有一个常数列表.我需要在数字列表中找到最接近x的数字.有关如何实现此算法的任何想法？

Answer 1

嗯,你不能这么快,O(N)因为你必须检查所有数字,以确保你有最接近的数字.也就是说,为什么不使用一个简单的变量找到最小值,寻找与x最小绝对差值的变量？

如果你可以说列表是从头开始排序的(它允许随机访问,就像数组一样),那么更好的方法是使用二进制搜索.当您在索引i处结束搜索(没有找到x)时,只需选择该元素及其邻居中的最佳元素.

Answer 2

我想这个数组是无序的.在订购它可以更快

我认为最简单和最快的方法是使用线性算法来查找最小值或最大值,但不是比较值,而是比较它与针之间差异的绝对值.

在C++中(我不能用C#但它会类似)代码看起来像这样:

// array of numbers is haystack
// length is length of array
// needle is number which you are looking for ( or compare with )

int closest = haystack[0];
for ( int i = 0; i < length; ++i ) {
  if ( abs( haystack[ i ] - needle ) < abs( closest - needle ) ) closest = haystack[i];
}
return closest;