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

Question

我在寻找亚马逊面试题时遇到了这个问题，想要问一下。

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

如果所有数字都是整数，则答案为从数组中的每个数字中减去该数字，然后查找具有最小绝对值的元素。

但是当涉及到浮点数时，应该相对更加复杂。

有任何想法吗？谢谢。

- Dogacan Sbdb

---

你为什么认为浮点数会改变算法？ - Mark Ransom

“Series” 究竟是什么意思？你能对其进行排序并使用二分查找吗？二分查找不应该在浮点数上出现问题。 - Kolmar

@MarkRansom 浮点数的问题在于精度有限。例如：1）x=1e100, arr=[-1, 1, 0]。答案应该是1，但所有差值的abs值都等于1e100；2）x = 1; arr = [-1e100, 1e100]。那么答案应该是1e100，但两个差值的abs都等于1e100。（而且在后一种情况下二分查找也无法帮助...） - Kolmar

@Kolmar 谢谢你提供那些启示性的例子。 - Mark Ransom

有人认为这可能与机器epsilon有关（如何估计和应用），就像这篇帖子：https://dev59.com/_W445IYBdhLWcg3wUoxe - shole

Answer 1

浮点数存在精度误差问题。但是，浮点数比较不受精度误差影响：因此，您可以在线性时间内正确地找到刚好比x大和刚好比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更接近与自身符号相同的值。）

- Kittsil