寻找一种算法（版本2维二进制搜索） [英] Looking for an algorithm (version of 2-dimensional binary search)

问题描述

简单的问题和已知的算法：

我有一个大阵列100名成员。第一个X的成员都为0，其余均为1求x。

I have a big array with 100 members. First X members are 0, and the rest are 1. Find X.

我解决它由二进制搜索：检查部件50，如果是0 - 检查会员75，等等，直到我发现相邻的0和1

I am solving it by a binary search: Check member 50, if it is 0 - check member 75, etc, until I find adjacent 0 and 1.

我找了同样的问题，在二维的优化算法：

我有2维数组100 * 100。这些成员是在行0-X和列0-Y是0，其余的都1.如何找到Y和X？

I have 2-dimensional array 100*100. Those members that are on rows 0-X AND on columns 0-Y are 0, and the rest are 1. How to find Y and X?

推荐答案

简单的解决方案：在X方向，然后在Y方向先去

Simple solution: go first in X-direction and then in Y-direction.

检查（0,50）;如果它是0，检查（0,75）;直到找到相邻的0和1，然后再从那里到Y方向。

Check (0,50); If it is 0, check (0,75); until You find adjacent 0 and 1. Then go to Y direction from there.

解决方法二：

检查部件（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）之间。使用二进制搜索查找框的高度。

Check member (50,50). If it is 1, check (25,25), until You find 0. Continue, until You find adjacent (X,X) and (X+1,X+1) that are 0 and 1. Then test (X,X+1) and (X+1,X). Neither or one of them will be 1. If neither, You are finished. If only one, say for example (X+1,X), then You know that the box's size is between (X+1,X) and (100,X). Use binary search to find box's height.

修改：正如克里斯指出，似乎简单的方法是快。

EDIT: As Chris pointed out, it seems that the simple approach is faster.

第二类解决方案（修改）：

Second solution (modified):

检查部件（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）。

Check member (50,50). If it is 1, check (25,25), until You find 0. Continue, until You find adjacent (X,X) and (X+1,X+1) that are 0 and 1. Then test (X,X+1). If it is 1, then do binary search on line (X,X+1)...(X,100). Else do binary search on line (X,X)...(100,X).

即使是这样我可能在这里费口舌。如果它会更快，然后可以忽略不计金额。这仅仅是理论上的乐趣。 ：）

Even then I am probably beating a dead horse here. If it will be faster, then by neglible amount. This is just for theoretical fun. :)

编辑2 作为Fezvez和克里斯所说的那样，二进制搜索共分两个最有效的搜索空间;我的方法把该地区1/4和3/4片。 Fezvez指出，这可以通过预先计算分割系数进行补救（但是这将是额外的计算）。在我的算法的修改版本，我选择的方向去哪里（X或Y方向），这也有效地把两个搜索空间，然后进行二进制搜索。总之，这表明，该方法将永远是一个有点慢。 （和更复杂的实现。）

EDIT 2 As Fezvez and Chris put it, binary search divides the search space in two most efficiently; My approach divides the area to 1/4 and 3/4 pieces. Fezvez pointed out that this could be remedied by calculating the dividing factor beforehand (but that would be extra calculation). In modified version of my algorithm I choose the direction where to go (X or Y direction), which effectively also divides the search space in two, and then conduct binary search. To conclude, this shows that this approach will always be a bit slower. (and more complicated to implement.)

感谢你，伊戈尔OKS，有趣的问题。 ：）

Thank You, Igor Oks, for interesting question. :)

这篇关于寻找一种算法（版本2维二进制搜索）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！