algorithm - 给定整数 n 的 n*(n+1)，有效地找到 n

Question

给定一个整数 k，对于正整数 n，已知其形式为 k = n * (n+1)，我想找到值 n。在数学上，解决方案是n = (sqrt(1+4*k)-1)/2，但直接实现它需要将中间值转换为浮点数，然后再转换回整数。例如，在 Go 中，这可以实现如下：

func NFromK(k int) int {
    return int((math.Sqrt(float64(1+4*k))-1)/2 + 0.5)
}

有没有更有效的方法？也许只能使用整数算术找到解决方案？

（在我的应用程序中，k 是存储 n 维单纯形的 n+1 个顶点的数组的长度。）

标签： algorithm

Answer 1

你可以只用整数来做到这一点，但我怀疑它会更有效。您可以尝试找到最大的 n，使得 n*n < k，这可以通过空间 1 - k/2 的二进制搜索来完成。