Looking for an algorithm (version of 2-dimensional

Question

Easy problem and known algorithm:

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

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.

I am looking for an optimized algorithm for the same problem in 2-dimensions:

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?

Answer 1

Use binary search on both dimensions and the 1D case:

1. Start with j=50. Now the 1-D array obtained by varying i is of the desired form - so find X from 1D case.
2. If X = 100 (i.e. no ones), then make j=75 (middle of the range in j dimension) and repeat.
3. If X < 100, then you have found it. All that is left is to fix i=X and find Y from the 1D case.

Answer 2

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

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

Second solution:

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):

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. :)

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.)

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

Answer 3

Run your binary search twice. First determine X by running binary search on the last row and then determine Y by running binary search on last column.

Answer 4

Edit : The optimal solution consists in two simple binary search.

I'm very sorry for the long and convoluted post I did below. What the problem fundamentally consists in is to find a point in a space that contains 100*100 elements. The best you can do is to divide at each step this space in two. You can do it in a convoluted way (the one I did in the rest of the post) But if you realize that a binary search on the X axis still divides the research space in two at each step, (the same goes for the Y axis) then you understand that it's optimal.

I still let the thing I did, and I'm sorry that I made some peremptory affirmations in it.

---

If you're looking for a simple algorithm (though not optimal) just run the binary search twice as suggested.

However, if you want an optimal algorithm, you can look for the boundary on X and on Y at the same time. (You have to note that the two algorithm have same asymptotical complexity, but the optimal algorithm will still be faster)

In all the following graphics, the point (0, 0) is in the bottom left corner.

Basically when you choose a point and get the result, you cut your space in two parts. When you think about it that is actually the biggest amount of information you can extract from this.

If you choose the point (the black cross) and the result is 1 (red lines), this means that the point you're looking for can not be in the gray space (thus must be in the remaining white area)

On the other hand, if the value is 0 (blue lines), this means that the point you're looking for can not be in the gray area (thus must be in the remaining white area)

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

The point you're looking for is either in rectangle 1, 2 or 3. You just need to check the two corners of rectangle 3 to know which of the 3 rectangle is the good one.

So the algorithm is the following :

• Note where are the bottom left and top right corner of the rectangle you're working with.

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

• Check the 2 other corners of the rectangle 3 (you'll necessary already know the values of the two corners on the diagonal) It is possible to check only one corner to know the right rectangle (but you'll have to check the two corners if the right rectangle is the rectangle 3)

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

• Repeat by reducing the problem to the good rectangle until the final rectangle is reduced to a point : it's the value you're looking for

---

Edit : if you want the supremum optimality, you'd not the when you choose the point (50, 50), you do not cut the space in equal part. One is three time bigger than the other. Ideally, you'll choose a point that cuts the space in two equal regions (area-wise)

You should compute once at the beginning the value of factor = (1.0 - 1.0/sqrt(2.0)). Then when you want to cut bewteen values a and b, choose the cutting point as a + factor*(b-a). When you cut the initial 100x100 rectangle at the point (100*factor, 100*factor) the two regions will have an area (100*100)/2, thus the convergence will be quicker.