searching a element in 2D array of m/n which is row and column [closed]

Question

You are given an 2D array of MxN which is row and column wise sorted. What is the efficient way to search for an element?

Answer 1

Start in the top right position v of the matrix. If it's the item x you're looking for, you're done. If v is less than the item you're looking for, move down. If v is greater than the item you're looking for, move left. Repeat until you hit the ends of the matrix.

Proof of correctness:

If the top right item is equal to x, there is nothing to prove. Consider two cases

v < x

In this case, we know that all of the elements in the top row are less than x. Thus, we can ignore the entire top row and move down.

Therefore, we can go from

  1 2 3 4 5 6
1 * * * * * v
2 * * * * * *
3 * * * * * * 
4 * * * * * *
5 * * * * * *

to

  1 2 3 4 5 6
1 . . . . . .
2 * * * * * v
3 * * * * * * 
4 * * * * * *
5 * * * * * *

That is, we end up with a smaller problem.

The other case is

v > x

In this case, we know that all of the elements in the right column are greater than x. Thus, we can ignore the entire right column and move left.

  1 2 3 4 5 6
1 * * * * * v
2 * * * * * *
3 * * * * * * 
4 * * * * * *
5 * * * * * *

to

  1 2 3 4 5 6
1 * * * * v .
2 * * * * * .
3 * * * * * .
4 * * * * * .
5 * * * * * .

Again, we end up with a smaller problem. By induction, we are done. This algorithm has time complexity O(m + n).

Edit:

Ted Hopp links to an absolutely beautiful extension of this idea that gives even better performance.

Here's the idea. In the algorithm that I gave above, the idea was that we could eliminate entire rows or columns from consideration at a time. The idea that he links to is to eliminate entire quadrants at time. The idea is simple

* * * * * *
* * * * * *
* * * * * * <- binary search
* * * * * *
* * * * * *

Binary search the middle row. This will give you the item, or a position that brackets the item you're looking for

* * * * * *
* * * * * *
* * * a|b * <- x between a, b
* * * * * *
* * * * * *

Now here is the key insight. The entire upper-left quadrant, and the entire lower-right quadrant can be immediately eliminated from consideration; all the elements in the upper left are less than a, all the elements in the lower-right are greater than b.

. . . . * *
. . . . * *
. . . a|b .
* * * * . .
* * * * . .

Now recurse on the two remaining pieces. Additionally, you can do the same procedure on the middle row or the upper-left to lower-right diagonal depending on which will yield the biggest gains.