c# - 快速查找遭受浮点不准确

Question

假设我有等间距的 double (64 位 float )x0,x1,...,xn .等距意味着对于所有 i , x(i+1) - xi是常数；称它为w宽度。

给定一个数字 y在 [x0,xn] 范围内我想找到最大的 i这样 xi <= y .

天真的方法会访问每个 i依次 ( O(n) )。稍微好一点的是使用二进制搜索 ( O(log n) )。

恒定时间查找将计算 (y-x0)/w并将其转换为整数。但是，由于浮点不准确，这偶尔会给出错误的结果。例如。假设从 0 开始有 100 个宽度为 0.01 的区间。

(int)(0.29/0.01) = 28 //want 29 here

我能否保留恒定时间查找但确保结果始终与二分查找相同？对于“w”和“x0”，使用小数而不是 double 执行计算似乎在这里可行，但它会一直有效吗？我总是可以通过与 x 的比较来跟踪直接查找两边都有，但这看起来很丑陋且效率低下。

为了澄清 - 我得到了 xi和值 y作为 double - 我无法改变这一点。但是在返回整数索引之前执行的任何中间计算都可以使用我喜欢的任何数据类型。此外，我可以执行一次性“准备”工作，以加快运行时计算速度。

编辑:抱歉 - 事实证明我没有正确检查“等距” - 当使用浮点运算计算它们的差异时，这些数字通常不是“等距”。

Answer 1

执行以下操作

计算 (int)(0.29/0.01) = 28//这里要 29

接下来，计算 28-1 和 28+1 之间的 i 的 i * 0.01 并选择正确的那个。