Looking for an algorithm (version of 2-dimensional binary search)

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

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.