寻找算法(二维二分搜索的版本)

Question

容易出问题和已知算法:

我有一个拥有100名成员的大阵容.前X个成员为0,其余为1.查找X.

我通过二分搜索来解决它:检查成员50,如果它是0 - 检查成员75等,直到我找到相邻的0和1.

我正在寻找一个针对二维相同问题的优化算法:

我有二维数组100*100.在0-X行和0-Y列上的那些成员是0,其余的是1.如何找到Y和X？

Answer 1

编辑:最佳解决方案包括两个简单的二进制搜索.

对于我在下面做的漫长而复杂的帖子,我感到非常抱歉.问题的根本在于在空间中找到包含100*100个元素的点.你能做的最好的事情是将这个空间的每一步分成两部分.你可以用一种复杂的方式(我在帖子的其余部分做的那样)但是如果你意识到X轴上的二分搜索仍然在每一步将研究空间分成两部分(对于Y来说也是如此) (轴)然后你明白它是最优的.

我仍然让我做的事情,我很抱歉我在其中做了一些强制性的肯定.

如果您正在寻找一种简单的算法(尽管不是最优的),只需按建议运行二次搜索.

但是,如果您需要最佳算法,则可以同时在X和Y上查找边界.(你必须注意,这两种算法具有相同的渐近复杂度,但最优算法仍然会更快)

在以下所有图形中,点(0,0)位于左下角.

基本上,当您选择一个点并获得结果时,您会将空间分成两部分.当你想到它实际上是你可以从中提取的最大量的信息.

如果选择点(黑色十字)并且结果为1(红线),则表示您要查找的点不能位于灰色空间中(因此必须位于剩余的白色区域中)

另一方面,如果值为0(蓝​​线),这意味着您要查找的点不能位于灰色区域(因此必须位于剩余的白色区域中)

所以,如果你得到一个0结果和一个1结果,这就是你将得到的:

您正在寻找的点是矩形1,2或3.您只需要检查矩形3的两个角来知道3个矩形中的哪一个是好的.

所以算法如下:

• 请注意您正在使用的矩形的左下角和右上角.

• 沿着矩形的对角线进行二分搜索,直到你在1个结果上偶然发现一次并且一次0结果.

• 检查矩形3的其他两个角(您必须已经知道对角线上两个角的值)可以只检查一个角来知道右边的矩形(但是你必须检查两个角如果右边的矩形是矩形3)

• 确定您要查找的点是否为矩形1,2或3

• 重复将问题减少到好的矩形,直到最后的矩形缩小到一个点:它是您正在寻找的值

编辑:如果你想要最高优先级,你不是在你选择点(50,50)的时候,你不会在相等的部分切割空间.一个比另一个大三倍.理想情况下,您将选择一个在两个相等区域(区域方向)切割空间的点

你应该在开头计算一次的值factor = (1.0 - 1.0/sqrt(2.0)).然后,当你要削减bewteen价值观a和b选择切削点作为a + factor*(b-a).当您在该点(100*因子,100*因子)处切割初始的100x100矩形时,两个区域将具有面积(100*100)/ 2,因此会聚将更快.

Answer 2

运行二进制搜索两次.首先通过在最后一行上运行二进制搜索来确定X,然后通过在最后一列上运行二进制搜索来确定Y.

Answer 3

简单的解决方案:首先在X方向上,然后在Y方向上.

检查(0,50); 如果是0,检查(0,75); 直到找到相邻的0和1.然后从那里转到Y方向.

二解决方案:

检查会员(50,50).如果是1,检查(25,25),直到找到0.继续,直到找到相邻(X,X)和(X + 1,X + 1)为0和1.然后测试(X,X) +1)和(X + 1,X).它们中的任何一个都不是1.如果不是,那么你就完成了.如果只有一个,例如(X + 1,X),那么你就知道盒子的大小介于(X + 1,X)和(100,X)之间.使用二进制搜索来查找框的高度.

编辑:克里斯指出,似乎简单的方法更快.

第二种解决方案(修改):

检查会员(50,50).如果是1,检查(25,25),直到找到0.继续,直到找到相邻(X,X)和(X + 1,X + 1)为0和1.然后测试(X,X) +1).如果是1,则在行(X,X + 1)...(X,100)上进行二分搜索.否则在线(X,X)上进行二分搜索......(100,X).

即便如此,我可能在这里击败了一匹死马.如果它会更快,那么可以忽略不计.这只是为了理论上的乐趣.:)

编辑2正如Fezvez和Chris所说,二分搜索将搜索空间划分为两个最有效的; 我的方法将面积分为1/4和3/4件.Fezvez指出,这可以通过预先计算分频因子来解决(但这将是额外的计算).在我的算法的修改版本中,我选择了去哪里的方向(X或Y方向),这实际上也将搜索空间分成两部分,然后进行二分搜索.总而言之,这表明这种方法总是会慢一点.(并且实施起来更复杂.)

谢谢你,伊戈尔奥克斯,有趣的问题.:)