Algorithm search (two-dimensional binary search version)

Question

Easy problem and well-known algorithm:

I have a large array with 100 members. The first X-members are 0, and the rest are 1. Find X.

I solve it by binary search: check element 50, if it is 0 - check element 75, etc., until I find the neighboring 0 and 1.

I am looking for an optimized algorithm for the same task in two dimensions:

I have a 2-dimensional array of 100 * 100. Those elements that are in rows 0-X AND on columns 0-Y are 0, and the rest are 1. How can I find Y and X?

Answer 1

A simple solution: first go in the X direction, and then in the Y direction.

Check (0.50); If it is 0, check (0.75); until you find the neighboring 0 and 1. Then go in the direction of Y.

The second solution:

Check participant (50.50). If it is 1, check (25.25) until you find 0. Continue until you find the neighboring (X, X) and (X + 1, X + 1), which are 0 and 1. Then check (X, X + 1) and (X + 1, X). None, none of them will be 1. If not one, you are done. If only one, say, for example (X + 1, X), then you know that the window size is between (X + 1, X) and (100, X). Use binary search to find the height of the window.

EDIT : As Chris noted, a simple approach seems to be faster.

Second solution (changed):

Check participant (50.50). If it is 1, check (25.25) until you find 0. Continue until you find the neighboring (X, X) and (X + 1, X + 1), which are 0 and 1. Then check (X, X +1). If it is 1, then do a binary search on the string (X, X + 1) ... (X, 100). Else do a binary search on the string (X, X) ... (100, X).

Even then, I’m probably beating a dead horse here. If it will be faster, then for an unimaginable amount. This is just for theoretical fun. :)

EDIT 2 . According to Fezwez and Chris, binary search divides the search space into two most efficiently; My approach divides the area into 1/4 and 3/4 parts. Fezvez noted that this could be fixed by first calculating the dividing factor (but this will be an additional calculation). In a modified version of my algorithm, I choose the direction where to go (direction X or Y), which effectively also divides the search space into two parts, and then conducts a binary search. In conclusion, this shows that this approach will always be a little slower. (and harder to implement).

Thank you Igor Oks for an interesting question. :)

Answer 2

Edit: The optimal solution consists of two simple binary searches.

I am very sorry for the long and confusing post I made below. The main problem is to find a point in the space containing 100 * 100 elements. The best you can do is divide this space into two parts at each step. You can do it in a complicated way (the one I did in the rest of the post). But if you understand that binary search on the X axis still divides the study space into two at each step (the same goes for the Y axis), then you understand that this is optimal.

I still admit what I did, and I'm sorry that I made some peremptory statements in it.

---

If you are looking for a simple algorithm (although not optimal), just run the binary search twice.

However, if you need an optimal algorithm, you can search for a boundary on X and on Y at the same time. (You should note that both algorithms have the same asymptotic complexity, but the optimal algorithm will still be faster)

In all the following graphs, the point (0, 0) is located in the lower left corner.

Basically, when you select a point and get the result, you reduce the space in two parts . When you think about it, this is actually the largest amount of information you can extract from it.

If you select a point (black cross) and the result is 1 (red lines), this means that the point you are looking for may not be in gray space (thus being in the remaining white area)

On the other hand, if the value is 0 (blue lines), this means that the point you are looking for may not be in the gray area (so it should be in the remaining white area)

So, if you get one result 0 and one result, this is what you get:

The point you are looking for is either in rectangle 1, 2 or 3. You just need to check the two corners of rectangle 3 to find out which of the three rectangles is good.

So, the algorithm is as follows:

• Notice where the lower left and upper right corners of the rectangle you are working with are located.

• Do a double search on the diagonal of the rectangle until you stumbled at least once on result 1 and once on result 0.

• Check the 2 other corners of rectangle 3 (you need to know the values ​​of the two angles diagonally). You can only check one corner to know the right rectangle (but you will need to check two corners if the right rectangle is a rectangle. 3)

• Determine if the point you are looking for is in rectangle 1, 2 or 3

• Repeat, reducing the problem to a good rectangle until the last rectangle is reduced to a point: this is the value you are looking for

---

Edit: if you want the optimal optimality of the supremum, you would not choose the point (50, 50), you will not reduce the space in equal parts. One is three times the size of the other. Ideally, you will choose a point that reduces space in two equal areas (in area)

You must first calculate the value factor = (1.0 - 1.0/sqrt(2.0)) . Then, when you want to cut the values ​​of a and b , select the cutting point as a + factor*(ba) . When you cut the initial 100x100 rectangle at a point (coefficient 100 *, coefficient 100 *), the two areas will have an area (100 * 100) / 2, so convergence will be faster.

Answer 3

Perform a double search twice. First determine X by performing a binary search in the last row, and then determine Y by performing a binary search in the last column.

Answer 4

Use binary search on both dimensions and 1D case:

• Let's start with j = 50. Now the one-dimensional array obtained by changing i has the desired form - so find X from the 1D case.
• If X = 100 (i.e. not), then do j = 75 (in the middle of the range in j-dimensional size) and repeat.
• If X <100, then you found it. It remains only to fix i = X and find Y from the 1D case.