algorithm - 寻找算法(二维二分查找的版本)

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 的其他 2 个角(您必须已经知道对角线上两个角的值)可以只检查一个角以了解正确的矩形(但您将如果正确的矩形是矩形，则必须检查两个角 3)

• 判断你要找的点是在矩形1、2还是3中

• 重复将问题缩小到好的矩形，直到最终矩形缩小到一个点:这就是您要查找的值

---

编辑:如果你想要最高最优性，当你选择点 (50, 50) 时，你不会将空间等分。一个比另一个大三倍。理想情况下，您将选择一个点来切割两个相等区域(面积)的空间

您应该在开始时计算一次 factor = (1.0 - 1.0/sqrt(2.0)) 的值。然后当你想在 a 和 b 之间进行切割时，选择切割点为 a + factor*(b-a)。当您在点 (100*factor, 100*factor) 切割初始 100x100 矩形时，两个区域的面积将是 (100*100)/2，因此收敛会更快。