给出一个数学链接的二维数组（NxM），是否可以创建log（N）log（M）搜索算法

Question

我已经生成了这个2D数组（NxM），其中所有列，行和对角线都可以通过公式生成。我只想知道是否可以在log（N）log（M）中运行的地方创建搜索算法？

此二维数组也是无限的，仅显示前10行/ 10列

使用的方程式为z = 2 * d * x-2 * x * y-y ^ 2，在这种情况下，d = 22，上轴为x，下轴为y。因此（1,1）= 41，（2,2）=76。目标是找到z，重复值应集中在最小的x上，尽管唯一值始终将成为搜索的焦点。

请注意，所有行，列和对角线将产生唯一的方程式，将行，列或对角线带到无穷大。

Answer 1

看起来它沿着列增加，而沿着行减少。如果是这样，那么答案将是沿着对角的锯齿形路径，没有其他明显的结构。

除非等式具有更多的结构，否则我不认为您可以尝试找到那条路径。该算法为O(n+m)。

Answer 2

也许我想念什么，但如果

z = 2*d*x - 2*x*y - y^2, d=22 

然后给定搜索目标z'就可以解决

z' = 2dx - 2xy - y^2
z' + y^2 = 2x(d - y)
x = (1/2) (z' + y^2) / (d - y)

其他约束条件是x，y是大于零的整数。这立即告诉您y是从1到d-1的整数（假设d是整数），并且y必须具有与z相同的奇偶校验（两者都是偶数，或者都是奇数）。

实际上，如果您可以按照上述标准选择y = d-1，则x =（1/2）（z'+ d ^ 2-2d +1）是一个解决方案；在您的示例中，考虑d = 22且z'=103。然后y = 21，x = 272，解决方案进行了检验（插入原始方程式中）。如果由于奇偶校验问题而无法选择d-1，则解决方案似乎不会那么整洁。我想这是有道理的，因为应该没有整数解的问题，例如d = 1和z'= 1，d = 2和z'= 2，等等。可能还有更多捷径。