插值搜索？

Question

我有一个统一的一维网格，其值为 {0.1, 0.22, 0.35, 0.5, 0.78, 0.92}。这些值从位置 0 到 5 的位置相等，如下所示：

value       0.1      0.22      0.35       0.5      0.78      0.92
             |_________|_________|_________|_________|_________|
    
position     0         1         2         3         4         5

现在我喜欢 extract/interpolated 值定位，比如说 2.3，应该是

val(2.3) = val(2)*(3-2.3) + val(3)*(2.3-2)
         = 0.35*0.7 + 0.5*0.3
         = 0.3950

那么我应该如何在 C++ 中以优化的方式进行呢？我在 Visual Studio 2017.

我可以想到二分查找，但是有没有更好的方法 methods/or 来完成这项工作？谢谢

Answer 1

您可以获得插值的整数部分，并使用它来索引您需要在其间进行插值的两个值。无需使用二进制搜索，因为您始终知道在哪两个值之间进行插值。如果可能发生，只需要注意值之外的索引。

这仅在值始终映射到从零开始的整数索引时有效。

#include <cmath>

float get( const std::vector<float>& val, float p )
{
  // let's assume p is always valid so it is good as index
  const int a = static_cast<int>(p); // round down
  const float t = p - a;
  return std::lerp(val[a], val[a+1], t); 
}

编辑：

std::lerp 是一个 c++20 特性。如果您使用早期版本，您可以使用以下应该足够好的实现：

float lerp(float a, float b, float t)
{
   return a + (b - a) * t;
}

插值搜索？

Interpolation search?

c++

algorithm

std