给定一个数字,如何在一系列浮点数据中找到最接近的数字

Question

我在寻找亚马逊的面试问题时想到了这个问题.

给定一个数字,如何在一系列浮点数据中找到最接近的数字？

如果一切都是整数,则answer减去数组中每个数字的数字,然后在数组中查找具有最小绝对值的元素.

但是当谈到浮点时,它应该是高度非暴力的.

阿尼的想法？谢谢.

Answer 1

浮点数的问题是舍入误差。x然而，浮点数的比较不会受到舍入误差的影响：因此，您可以正确地找到比线性时间更大和更小的数字：

sm = -inf;
bg = inf;
for(i from 0 to n)
  if(arr[i] > x && arr[i] < bg)
    bg = arr[i];
  if(arr[i] < x && arr[i] > sm)
    sm = arr[i];

现在您只需确定这两个数字中哪个更接近x。由于bg较大且sm较小，因此唯一可能出现舍入误差的情况是当bg >> x或 时x >> sm；在这两种情况下，它只会增加舍入差值的大小。

（如果大小相同，例如如果x=1和arr=[1e100, -1e100]，您可以知道 更x接近于与自身具有相同符号的值。）