Find element in 2D sorted sorted array.

[SURI]

May be this older puzzle but worth solving this.

Given 2d sorted array (Sorted by columns and rows), What is the best
way to find an element?

e.g.
55 30 13
44 22 7
12 6 3

[Shyam Prakash]

Start at Top Right => current cell

If the "search value == value[current cell]", print found.
If search "value > value[current cell]", move towards left and make it
current cell.
If search "value < value[current cell]", move towards down and make it
current cell.

If it can't progress, print not found.

Worst case Complexity for [m x n] matrix = O(m + n)

Can we apply binary search on this? will have to check.

Thanks
Shyam Velupula

On Jul 7, 1:43 pm, SURI <koorella.s...@gmail.com> wrote:
> May be this older puzzle but worth solving this.
>

> Given2dsorted array (Sorted by columns and rows), What is the best

[SURI]

good explanation Shayam,

I guess we cannot apply binary search as it is, since the structure is
not recursive structure. But we can eliminate the (n+m)/4 elements on
first step and recursively solve 3 eligible sub structures of size (n
+m)/4 each INDEPENDENTLY.

Is this approach better than O(m+n) ?

-- SURI

[Shyam Prakash Velupula]

Yes the approach you mentioned (eliminating one quarter every iteration) will yield better complexity.

On the side note, you played with numbers and my name :-)

No. elements eliminated would be => (n * m) / 4

--
You are limited only by your imagination

[SURI]

Ooooops .. It is a typo, Yes it is (n*m)/4.