CareerCup

do a binary search on (0,0) and (m,m ) i.e. (5,5) , when diagonal search could not find the number and we end up with one diagonal position say (p,q), then we have to search that particular row (row q) (from 0 to p) and column (column q) for that number. we can use binary search here too

Say we have a mxn matrix. Pick the m/2 nd row. Find the median using the quick-select algo. Now this median is larger than all the elements in the top-left m/2xn/2 matrix and lesser than all the elements in the bottom-right m/2xn/2 matrix. So if the target is less than the median we dont have to look at the elements in the bottom-right and if the target is greater than the median we dont have to look at elements in the top left. Do this recursively on the smaller matrices we get till we find the target.I think the recurrence will come out to be some thing like T(n)=3T(mn/4)+m.any thoughts?

Assume columns are sorted ascending top to bottom and rows ascending left to right.

Start with bottom left element. If given element is greater, eliminate the column, else if lesser, eliminate the row.

Pick bottom left of resulting matrix.

O(m+n) time algo. This is a pretty standard problem and the solution is pretty standard too.

int findElement(Matrix M, int val)
{
int i,j;
for(i=0, j=n-1;i<m && j>=0;)
{
if(M[i][j]==val){
return 1;
else if(M[i][j]<val)
j--;
else if(M[i][j]>val)
i++;
}
return 0;
}

{{
bool search(int key, int i = 0, int j = 0, int m = M, int n = N)
{
if (i >= m || j >= n)
return false;
int x = (i + m) / 2,
y = (j + n) / 2;
int v = matrix[x][y];
if (v == key)
return true;
if (key > v)
return search(key, i, y + 1, m, n) || search(key, x + 1, j, m, n);
// key < v
return search(key, i, j, m, y) || search(key, i, j, x, n);
}
}}

bool search(int key, int i = 0, int j = 0, int m = M, int n = N)
{
    if (i >= m || j >= n)
        return false;
    int x = (i + m) / 2, 
        y = (j + n) / 2;
    int v = matrix[x][y];
    if (v == key)
        return true;    
    if (key > v)
        return search(key, i, y + 1, m, n) || search(key, x + 1, j, m, n);
    // key < v
    return search(key, i, j, m, y) || search(key, i, j, x, n);
}

LOler is correcct fully .
Read chazzzz solution .... suppose m*m matrix (haven't generalized as maybe wrong !!)
x = element to find
now compare with a[m/2][m] if x > this (case 1)remove all the rows <m/2 else remove all the rows >m/2 (case 2)

now accordingly case 1: compare with a[m][m/2]
case 2: compare with a[0][m/2]

Maybe now reduced to m/2*m/2 array ie t(m) = t(m/2) + o(1) !!!!

I like chaz's solution alongwith LOLer's approach. Both are correct in finding the element efficiently. Rest sucks!

Hey just curious if this will work.

Let the element to searched (say r) be compared with middle row's last element (A[M/2][N]). If r is greater, then we check in the bottom matrix A[M/2+1,0] to A[M,N], else we check in the top matrix A[o,o] to A[M/2,N].