将数字拟合到序列中的一般方法

Question

一般问题如下。给定一个递增的正整数序列 0 < s_1 < s_2 < s_3 < ... 和一个正整数 n，是否有一种有效的算法来找到（唯一）索引 k 使得 s_k <= n < s_(k+1)?

这个问题的具体例子有一个特别好的解决方案是找到二进制扩展的最大非零数字，即取s_i = 2^(i-1)，然后k = log_2(n)。

一个稍微难点的例子是在阶乘展开中找到最大的非零数字，即取 s_i = i!.

我想到的提出这个问题的例子如下：

s_i = i第三角数= 1 + 2 + ... + i = i(i+1)/2

我想要一个很好的解决方案，意思是比下面的更好

for(int i=1; ; ++i) {
  if (triangle[i] > n)
    break;
}
return i;

注意：这里不能使用二进制搜索，因为序列是无限。当然，有一个明显的限制，即 k <= n，但总的来说，这是一个可怕的限制。例如，如果 s_i = i!，则在 n=20 上使用二进制搜索需要在答案为 k=3 时计算 20!，因此不需要计算超过 [=17] =].

Answer 1

一般方法：尝试求解方程 n = s(x) 和集合 k = floor(x)。

对于 s_i=2^(i-1) 你得到 x=log2(n)+1。 s_i=i*(i+1)/2 你得到 x=(sqrt(1+8n)-1)/2.

如果方程无法解析求解，请尝试近似（例如 Newton's method），或者简单地对序列使用二进制搜索。

General method to fit a number into a sequence